Экономическая интерпретация двойственной задачи

Составим и решим симплексным методом задачу, двойственную задаче об использовании сырья, сформулированной в 2.4 (см. пример 4). Экономико-математическая модель формулируется так: найти максимум функции F= 6х₁ + + 2х₂ + 2,5х₃ + 4х₄, выражающей прибыль предприятия, при следующих ограничениях:

Решение задачи симплексным методом привело к следующему результату: максимальное значение функции F, равное 1050 ден. ед., достигается при оптимальном решении (0, 225, 0, 150, 475, 0, 0). Первые четыре компоненты этого решения дают оптимальный план выпуска продукции, а последние три -остатки сырья видов I, II и III.

Рассмотрим эту задачу как исходную и составим двойственную ей. Матрица В условий прямой задачи и матрица В’ - транспонированная матрица В - имеют следующий вид:

	5	1	0	2	1000			5	4	1	6
B=	4	2	2	1	600		B’=	1	2	0	2
	1	0	2	1	150			0	2	2	2.5
	6	2	2.5	4	Fmax			2	1	1	4
								1000	600	150	Zmin

В двойственной задаче нужно найти минимум функции

Z = 1000y₁ + 600y₂ +150,

при ограничениях

Систему ограничений-неравенств двойственной задачи обратим в систему уравнений:

Применив теперь алгоритм симплекс-метода, решим поставленную задачу: Z_min= 1050. Оптимальное решение (0; 1; 3; 1; 0; 5.5; 0).

Запишем соответствующие переменные прямой и двойственной задач:

x1   x2  x3  x4                y4      y5      y6 y7

x5 x6   x7                 y1      y2  y3

Компоненты у₁, у₂, у₃ оптимального решения двойственной задачи оценивают добавочные переменные х₅, х₆, х₇ прямой задачи.

Равенство нулю переменной у₁ в оптимальном решении свидетельствует о том, что переменная х₅ положительна в оптимальном решении прямой задачи, или что подстановка компонент оптимального решения в первое неравенство системы ограничений прямой задачи не обращает его в строгое равенство.

Переменные у₂, у₃ положительны, а соответствующие им переменные прямой задачи х₆, х₇ равны нулю в оптимальном решении прямой задачи. Подстановка компонент оптимального решения во второе и третье неравенства прямой задачи обращает их в строгие равенства.

Экономический смысл этого обстоятельства состоит в том, что сырья вида I у нас имеется с излишком и мы не особенно «дорожим» им, поэтому устанавливаем для него нулевую оценку, а вот сырье видов II и III является дефицитным, оно все целиком расходуется, поэтому мы оцениваем эти виды сырья некоторыми положительными оценками (у₂ = 1, у₃ = 3).

Как оценить единицу сырья каждого вида в зависимости от той прибыли, которую приносит предприятию реализация продукции А₁, А₂, А₃, А₄? Подчеркнем, что речь идет не о стоимости сырья при его приобретении предприятием. Нас интересует относительная стоимость сырья с точки зрения получения максимальной прибыли при изменении его запасов. Ясно, что ценность того или иного вида сырья будет определяться величиной роста максимальной прибыли при увеличении, например  запаса сырья i-го вида.

Cогласно выводу из теоремы об оценках DF_max = y_iDb_i.

В этой формуле у_i -компонента оптимального решения двойственной задачи. Здесь особенно ощутимо видна стоимостная сущность переменных двойственной задачи. Они выступают как условные цены единицы i-го вида сырья. Поэтому переменные двойственной задачи часто называют объективно обусловленными оценками.

Вернемся к оптимальному плану двойственной задачи. При этом нас будут интересовать только первые три компоненты: у₁ = 0, у₂ = 1, у₃ = 3 этого решения, которые соответствуют добавочным переменным прямой задачи х₅, х₆, х₇, выражающим величины остатков сырья видов I, II, III.

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

Пусть запас сырья вида I увеличился на 100 усл. ед. Пользуясь формулой (5.3), получим

DF_max = y₁Db₁ = 0_*100 = 0,

т. е. прибыль не увеличится, оптимальное решение не изменится. Последний вывод закономерен, ибо выпуск продукции в условиях прямой задачи лимитируется наличием сырья видов II, III.

Увеличим на 100 ед. запас сырья вида II. Тогда

DF_max = y_2*100 = 1_*100 = 100 ден. ед.

Решая прямую задачу симплексным методом (рекомендуется сделать самостоятельно) с измененной правой частью второго ограничения-неравенства: 4х₁ + 2х₂ + 2х₃ + х₄  700, получим оптимальное решение

(0, 275, 0, 150, 425, 0; 0).

Увеличив на 100 усл. ед. запас сырья III, получим

DF_max = y_3*100 = 3_*100 = 300 ден. ед.

При этом измененном условии максимальная прибыль равна 1350 усл. ед. при оптимальном плане (0, 175, 0, 250, 325, 0, 0). В справедливости последнего утверждения можно убедиться, решив симплексным методом прямую задачу с измененной правой частью третьего ограничения-неравенства: х₁ + 2х₃ + х₄ £ 250.

Примеры решения заданий

Пусть необходимо найти оптимальный план производства двух видов продукции Р и R, то есть такой план, при котором целевая функция (общая прибыль) была бы max, а имеющиеся ресурсы использовались бы наилучшим образом.

Таблица 2.1

Данные о запасе и нормах расхода ресурсов

Типы ресурсов	Норма расхода ресурса на ед.		Объем ресурса (запасы)
	P	R
A	2	1	12
B	0,1	0,5	4
C	3,5	1	18
Прибыль на ед. изделия	4	5	-

Требуется:

I. Cформулировать экономико-математическую модель задачи в виде ОЗЛП.

II. Привести ОЗЛП к канонической форме.

III. Сформулировать экономико-математическую модель задачи двойственной к исходной.

IV. Построить многогранник решений (область допустимых решений) и найти оптимальную производственную программу путем перебора его вершин и геометрическим способом.

V. Решить задачу с помощью симплекс-таблиц.

Решение:

I. Оптимизационная модель задачи запишется следующим образом:

а) целевая функция

б) ограничения:

в) условия неотрицательности переменных х₁≥0; х₂≥0.

II. Приведем ОЗЛП к канонической форме. Для этого введем дополнительные переменные x ₃, x ₄ и x ₅.

а) целевая функция

б) ограничения:

в) условия неотрицательности переменных .

III. Сформулируем экономико-математическую модель задачи двойственную к исходной. Матрица В условий прямой задачи и матрица В’ – транспонированная матрица В – имеют следующий вид:

	2	1	12			2	0,1	3,5	4
B=	0,1	0,5	4		B’=	1	0,5	1	1
	3,5	1	18			12	14	18	Zmin
	4	1	Fmax

В двойственной задаче нужно найти минимум функции

Z = 12y₁ + 14y₂ +18y₃, при ограничениях

Систему ограничений-неравенств двойственной задачи обратим в систему уравнений:

Компоненты у₁, у₂, у₃ оптимального решения двойственной задачи оценивают добавочные переменные х₃, х₄, х₅ прямой задачи.

VI. Построим многогранник решений (область допустимых решений) и найдем оптимальную производственную программу путем перебора его вершин и геометрическим способом.

Преобразуем нашу систему ограничений, найдя в каждом из уравнений х₂ и отложим их на графике. Любая точка на данном графике с координатами х₁, х₂ представляет вариант искомого плана. Однако ограничения по ресурсу А сужают область допустимых решений. Ими могут быть все точки, ограниченные осями координат и прямой, так как не может быть израсходовано ресурса больше, чем его на предприятии имеется. Если точки находятся на самой прямой, то ресурс используется полностью. Аналогичные рассуждения можно привести для ресурсов В и С. В результате условиям задачи будет удовлетворять любая точка лежащая в пределах заштрихованного многоугольника. Данный многоугольник называется областью допустимых решений.

Определим точки пересечения линий ограничений с осями:

1) : (0;12) и (6; 0);

2) : (0; 8) и (40; 0);

3) : (0; 18) и (5,14; 0);

Однако нам необходимо найти такую точку, в которой достигался бы max целевой функции.

Оптимальную производственную программу можно найти двумя способами:

1) путем перебора его вершин

Находим координаты вершин многоугольника ABCDE и подставляя в целевую функцию находим ее значение.

А: А (0; 0)          Z(A) =4×0+5×0=0

В: В (0; 8)          Z(B) = 4×0+5×8=40

С: – это пересечение первого и второго уравнений

; ; -9 x ₂=-68 x ₂=7,555; x ₁=2,222.

С (2,22; 7,55)     Z(C) = 4×2,22+5×7,55=8,88+37,77=46,65

 

D: – это пересечение первого и третьего уравнений

; 1,5 x ₁=6; x ₁=4; x ₂=4.

D (4; 4)                Z(D)=4×4+5×4=20+25=45

E: (5,14; 0)         Z(E) = 4×5,14+5×0=20,56

Находим max значение целевой функции. Оно находится в точке
С (2,22; 7,55). Таким образом max прибыль составит 46,65 у.д.е. при выпуске продукта Р в количестве 2,22 у.е. и R – 7,55 у.е.

2) геометрическим способом

Целевая функция геометрически изображается с помощью прямой уровня, т.е. прямой на которой Z=C₀+C₁X₁+C₂X₂ – принимает постоянное значение.

Если С – произвольная const, то уравнение прямой имеет вид

C₀+C₁X₁+C₂X₂=С

При изменении const С получаем различные прямые, параллельные друг другу. При увеличении С прямая уровня перемещается в направлении наискорейшего возрастания функции Z, т.е. в направлении ее градиента. Вектор градиента

Точкой min Z будет точка первого касания линии уровня с допустимым многоугольником. Точкой max – точка отрыва линии уровня от допустимого многоугольника. Эти точки чаще всего совпадают с некоторыми вершинами допустимого многоугольника, хотя их может быть и бесчисленное множество, если линия уровня Z параллельна одной из сторон допустимого многоугольника. Это точка С (2,22; 7,55)

Z=46,65 у.д.е.

VII. Решим задачу с помощью симплекс-таблиц.

Пусть необходимо найти оптимальный план производства двух видов продукции P и R.

1. Построим оптимизационную модель:

F(X)=4X₁+5X₂→max                  

1. Преобразуем задачу в приведенную каноническую форму. Для этого введем дополнительные переменные X₃, X₄ и X₅.

F(X)=4X₁+5X₂→max                  

Построим исходную симплекс-таблицу и найдем начальное базисное решение.

Баз. пер.	Своб. член	Х1	Х2	Х3	Х4	Х5
Х3	12	2	1	1	0	0
Х4	4	0,1	0,5	0	1	0
Х5	18	3,5	1	0	0	1
F	0	– 4	– 5	0	0	0

Базисное решение (0; 0; 12; 4; 18). F=0.

Находим генеральный столбец и генеральную строку

. Генеральный элемент 0,5.

Баз. пер.	Своб. член	Х1	Х2	Х3	Х4	Х5
Х3	4	1,8	0	1	2	0
Х2	8	0,2	1	0	2	0
Х5	10	3,3	0	0	-2	1
F	40	– 3	0	0	-10	0

Базисное решение (0; 8; 4; 0; 10). F=40.

2,22222. Генеральный элемент 1,8.

Баз. пер.	Своб. член	Х1	Х2	Х3	Х4	Х5
Х1	2,22	1	0	0,55	1,11	0
Х2	7,56	0	1	-0,11	1,77	0
Х5	2,74	0	0	1,82	5,63	1
F	46,65	0	0	-1,665	-13,3	0

Базисное решение (2,22; 7,56; 0; 0; 2,74). F=46,65.

Эта таблица является последней, по ней читаем ответ задачи. Оптимальным будет решение (2,22; 7,56; 0; 0; 2,74), при котором F_max =46,65, т.е. для получения наибольшей прибыли, равной 46,65 денежных единиц, предприятие должно выпустить 2,22 единиц продукции вида P и 7,56 единиц продукции вида R, при этом ресурсы A и B будут использованы полностью, а 2,74 единиц ресурса С останутся неизрасходованными.