Методы линейного программирования

В таблице 2 приведена двойственная задача к рассматриваемой задаче планирования производства продукции.

 

Таблица 2- Исходная и двойственная задачи

Исходная задача	Двойственная  задача
	(1.11)              (1.12) .                     (1.13)

 

Рассмотрим экономический смысл двойственной задачи. Допустим, что у предприятия есть возможность реализации всех своих ресурсов некоторой организации вместо того, чтобы организовывать свое производство. Необходимо установить прикидочные цены на ресурсы. Обозначим - цена единицы ресурса i-го вида (где ). Эти цены должны быть установлены исходя из несовпадающих интересов предприятия и покупающей организации [5, c 24].

Общую стоимость  ресурсов покупающая организация стремится  уменьшить, что дает основание записать целевую функцию задачи:

 

 

F_Д=b₁×z₁+ b₂×z₂+…+ b_m×z_m®min

 

Предприятие согласно продать  ресурсы только по таким ценам, при которых оно получит за них выручку не меньшую той суммы, которую могло бы получить, организовав собственное производство. Таким образом, предприятие откажется от выпуска продукции j-го типа, если

 

   ( ).

 

 

 

 

В результате получим систему  ограничений по каждому виду  продукции (1.12). По смыслу цена неотрицательна, поэтому в двойственную задачу включаются ограничения неотрицательности (1.13).

В отчетах Excel, получаемых с помощью надстройки “Поиск решения” оптимальное значение двойственной переменной называется теневой ценой. Теневая цена - это оценка значимости ресурса, вытекающая из конкретных условий задачи, а не реальная цена на рынке [2, c 26].

1.6 Первая теорема двойственности

Если существует единственное решение исходной задачи, то существует и единственное решение двойственной задачи, причем значения целевых функций на оптимальных решениях совпадают:

max F=min F_Д .

Это означает, что  предприятию безразлично, производить  ли продукцию по оптимальному плану X^* и получить максимальную прибыль, либо продать ресурсы по оптимальным ценам Z^* и получить такую же сумму. Для всех других (неоптимальных) планов X и Z прибыль от выпуска продукции всегда меньше внутренней стоимости затраченных ресурсов: F<F_Д, а величина F_Д-F характеризует производственные потери.

Следствие (теорема об оценках).

Двойственная оценка z_i^* (теневая цена) показывает, как изменится целевая функция исходной задачи при изменении ресурса b_i на единицу:

Таким образом, по теневым ценам можно судить о том, насколько целесообразно изыскивать резервы для увеличения количества i-го ресурса: если соответствующая теневая цена равна нулю, то увеличение количества этого ресурса никак не повлияет на рост прибыли. С другой стороны, чем  больше теневая цена, тем больше увеличится прибыль при увеличении количества этого ресурса на одну единицу. Поэтому тот ресурс, который имеет большую теневую цену, считается более дефицитным [5, c 30].

Однако эта  теорема справедлива  только тогда, когда при изменении количества ресурса b_i значения переменных z_i^* в оптимальном плане двойственной задачи остаются неизменными. Это выполняется в пределах устойчивости оптимального решения, т.е. когда структура решения не изменяется. Пределы устойчивости при изменении правых частей ограничений указаны во второй таблице отчета по устойчивости (рис. 8).

1.7 Понятие нормированной стоимости

Ограничения двойственной задачи можно также привести к  виду равенства, введя дополнительные переменные v_j, которые вычитаются из левых частей ограничений:

 

                                                                   (1.14)

 

Экономический смысл дополнительных двойственных переменных v_j ( ) следующий: это потери при производстве единицы продукции j-го типа. В самом деле, дополнительная двойственная переменная v_j может быть представлена в виде следующего равенства:

 

 

 

                                       

 

 

 

 

Таким образом, v_j – это разница между той суммой, что могли бы получить, продавая ресурсы, необходимые для производства единицы продукции типа j, и прибылью, которая будет получена, если из этих ресурсов произвести и продать продукцию.

v_j=0, если оценка затрат ресурсов равна прибыли, т.е. потерь при производстве нет.

v_j>0, если оценка затрат ресурсов больше прибыли от единицы продукции. В этом случае производить этот вид продукции невыгодно.

В отчетах Excel  оптимальное значение дополнительной двойственной переменной называется нормированной стоимостью.

Нормированная стоимость также показывает, насколько  уменьшится целевая функция при  принудительном выпуске единицы  продукции соответствующего типа [3, c 41].

Пусть, например, продукция вида j не вошла в оптимальный план производства, т.е. =0. Однако существует некоторое плановое задание, предписывающее выпуск этого вида продукции в количестве T_j единиц. Тогда при выпуске этого невыгодного вида продукции на него будут оттянуты ресурсы, и выгодной продукции будет выпущено меньше. Целевая функция (общая прибыль) уменьшится, причем это уменьшение можно количественно измерить:

 

.

 

2 ПОСТАНОВКА ЗАДАЧИ

Цех мебельного комбината выпускает трельяжи, трюмо и тумбочки под телевизоры. Норма расхода материала в расчете на одно изделие, плановая себестоимость, оптовая цена предприятия и трудоемкость единицы продукции приведены в таблице 3. При этом запас древесностружечных плит, досок еловых и березовых – 90, 30 и 14 м³ соответственно. Плановый фонд рабочего времени – 16800 чел/час. Необходимо составить план производства мебели, максимизирующий прибыль.

 

Таблица 3- Исходные данные

Ресурсы	Норма расхода  ресурса на одно изделие
	Трельяж	Трюмо	Тумбочка
Древесностружечные  плиты, м3	0,032	0,031	0,038
Доски еловые, м3	0,02	0,02	0,008
Доски березовые, м3	0,005	0,005	0,006
Трудоемкость, чел/час	10,2	7,5	5,8
Плановая себестоимость, у.е.	88,81	63,98	29,60
Оптовая цена предприятия, у.е.	93,00	67,00	30,00

 

Вопросы:

1. Какие виды продукции необходимо выпускать мебельному комбинату? Какую сумму прибыли получит предприятие от выпуска продукции?
2. Какие ресурсы являются дефицитными при данном производстве?
3. Как изменится прибыль от выпуска продукции при увеличении запаса досок еловых на 5 м³?
4. К чему приведет задание плана  выпуска по тумбочкам в количестве 100 штук?

 

 

 

 

 

3 РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО  ПРОГРАММИРОВАНИЯ

Составим математическую модель задачи. Для этого:

а) Введем переменные. Нужно найти план производства, т.е. количество мебели каждого вида, которые следует производить. Таким образом, будет 3 переменных:

x₁- количество трельяжей;

x₂ –количество трюмо;

x₃ –количество тумбочек.

б) Запишем целевую функцию. Она должна выражать собой критерий оптимальности (т.е. тот показатель, который в задаче должен достигнуть максимума или минимума). В нашей задаче указано, что должна быть максимальна прибыль. Поэтому целевая функция должна представлять собой формулу расчета прибыли. 

Прибыль от реализации продукции рассчитывается, как оптовая цена минус плановая себестоимость. Поэтому прибыль от реализации единицы трельяжа составляет 4,19 ден. ед. (93-88,81), трюмо – 3,02 ден. ед. (67-63,98), тумбочки 0,4 (30-29,60) ден. ед.

Поскольку мы собираемся выпускать x₁ трельяжей, прибыль от них составит 4,19x₁ денежных единиц. Аналогично прибыль от трюмо равна 3,02x₂ , и т.д. Общая прибыль от всех изделий равна сумме:

F=4,19x₁+3,02x₂+0,4x₃→ max

в) Запишем систему ограничений. Расход каждого вида ресурса не должен превышать его запас. Расход древесностружечных плит на производство трельяжей равен 0,32x₁, на трюмо – 0,031x₂, и т.д. Общий расход древесностружечных плит выражается с помощью формулы: 0,32х₁+0,031х₂+0,038х₃, а запас равен 90. Поэтому имеем неравенство: . Аналогично записываются другие ограничения. 

Математическая модель задачи имеет следующий вид:

 

 

 

 

 

 

 

 

Здесь x_j – количество выпускаемой продукции j-го типа (j= ).  Целевая функция представляет собой общую прибыль от производства продукции. Ограничения отражают конечность запасов ресурсов на предприятии. Неотрицательность переменных следует из их смысла.

Приведем исходную задачу к каноническому виду:

 

 

 

 

 

 

 

 

Дополнительные  переменные y_i есть остатки ресурсов каждого вида. Т.е. y₁ – это остаток древесностружечных плит, y₂ – остаток досок еловых и т.д.

Составим двойственную задачу:

 

 

 

 

 

 

Двойственные  переменные z_i - это оценки ресурсов задачи (теневые цены).

В двойственной задаче приведем ограничения к виду равенства, вычитая из левых частей ограничений дополнительные переменные:

 

 

 

 

 

 

Дополнительные  двойственные переменные v_j есть потери при производстве единицы продукции j-го типа.

 

 

 

Решим данную задачу с помощью надстройки MS Excel “Поиск решения”.

Исходные данные представлены в виде таблицы, которая содержит формулы вычисления целевой функции, левых и правых частей ограничений. Ячейки, которые отведены под значения переменных, называются изменяемыми. В них введены начальные приближения для переменных (нулевые). Когда надстройка “Поиск решения” закончит вычисления, в эти ячейки будут записаны найденные оптимальные значения переменных.

Выполним  следующую последовательность:

1. Подготовка исходных данных задачи на листе Excel. Оформление исходных данных для надстройки “Поиск решения” показано на рисунке 1.

Изменяемыми ячейками будут ячейки A3:С3, которые отведены под значения переменных. В них введены начальные значения переменных (нулевые).

 

 

 

 

 

 

 

 

Рисунок 1- Лист Excel с исходными данными и формулами для решения задачи с

помощью надстройки “Поиск решения”

Целевой ячейкой  будет являться ячейка D5, которая содержит формулу вычисления значения целевой функции (т.е, прибыли от продажи стульев шести типов). При большом числе переменных эту формулу удобно задавать с помощью стандартной функции Excel СУММПРОИЗВ(). Выбрав ее название в меню, заполняем окно параметров. При этом Массив 1 – это диапазон коэффициентов целевой функциии, а Массив 2 – диапазон изменяемых ячеек. Функция СУММПРОИЗВ() соответствующие ячейки диапазонов перемножает и находит сумму этих произведений. Например, формула в ячейке D5 записана в виде CУММПРОИЗВ(A5:C5;A3:C3), что соответствует формуле расчета прибыли 4,19x₁+3,02x₂+0,4x₃.

 В ячейки D7:D10 введены формулы вычисления левых частей ограничений (расход ресурса каждого вида).  Они также заданы с помощью функции СУММПРОИЗВ().

2.  Вызов надстройки “Поиск решения” выполняется командой Сервис/Поиск решения.

3. Задание условий поиска. В окне “Поиск решения”   указываем адрес целевой ячейки (D5) и цель, которая должна быть достигнута (максимальное значение целевой функции), адреса изменяемых ячеек (в которых “Поиск решения” должен подобрать значения), а также задаем ограничения задачи (рисунок 2).

 

 

 

 

 

 

 

 

 

 

Рисунок 2- Окно “Поиск решения” для задачи планирования производства