Примечание
В случае, когда среди векторов Р1, Р2,…, Рn+m, составленных из коэффициентов при неизвестных в системе уравнений (3.15), имеется m единичных, указанную матрицу P-1 образуют числа первых m строк последней симплекс-таблицы, стоящие в столбцах данных векторов, а оптимальный план двойственной задачи Y* определяется по следующему правилу:
, если ci = 0 , если ci ≠ 0 |
для всех , где i – элемент (m+1)-ой строки столбцов единичных векторов первоначального базиса.
Пример 3.10
Рассмотрим задачу об использовании сырья (пример 2.1). Найдем оптимальный план соответствующей двойственной задачи (пример 3.5). Решение прямой задачи приводится в разделе 3.4 (см пример 3.3).
Рассмотрим последнюю симплекс-таблицу:
i | Базис | Сб | Р0 | 3 | 2 | 0 | 0 | 0 | 0 |
Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | ||||
Х2 | 4/3 | 2/3 | -1/3 | ||||||
Х1 | 10/3 | -1/3 | 2/3 | ||||||
Х5 | -1 | ||||||||
Х6 | 2/3 | -2/3 | 1/3 | ||||||
38/3 | 1/3 | 4/3 | |||||||
у*5 | у*6 | у*1 | у*2 | у*3 | у*4 |
Воспользуемся Теоремой 3.3 для нахождения Y*.
Матрицу Р образуют вектора Р2 , Р1, Р5, Р6, соответствующие базисным переменным последней симплекс-таблицы, взятые из исходной системы уравнений:
х1 + 2х2 + х3 =6
2х1 + х2 +х4 =8
-х1 + х2 +х5 =1
х2 +х6 =2
то есть : Р2 Р1 Р5 Р6
2 1 0 0
Р = 1 2 0 0
1 -1 1 0
1 0 0 1
Сб = (2;3;0;0).
Таким образом,
Очевидно, что данное оптимальное решение Y* легче получить, воспользовавшись приложением к Теореме 3.8.
Действительно, так как исходная задача имеет 4 единичных вектора Р , Р1, Р5, Р6, то обратная матрица Р-1 будет записана в первых 4-х строках последней симплекс-таблицы (в столбцах переменных Х3, Х4, Х5, Х6), значения двойственных переменных – в тех же столбцах последней 5-й строки (поскольку Сi=0, i = 3,4,5,6).
Итак, анализируя оптимальное решение двойственной задачи, можно сделать следующие выводы:
1) 1й и 2ой ресурсы (продукты А и В) являются дефицитными, так как соответствующие им двойственные переменные у*1 =1/3 и у*2=4/3 положительны, причем, продукт В более дефицитный (у*2 > у*1) ;
2) 3й и 4й ресурсы (ограничения на спрос) не дефицитны (у*3 = у*4=0). В частности, подобную информацию можно получить с помощью оптимальных дополнительных переменных прямой задачи, которые численно выражают разность между двумя частями соответствующих ограничений: Х3=Х4=0 – остаток у дефицитных ресурсов отсутствует, Х5=3, Х6=2/3 – величина дисбаланса между спросом на товар и объемом его производства;
3) кроме того, дополнительные двойственные переменные у*5 = у*6 = 0 характеризует рентабельность выпускаемой продукции соответственно Е и I. Они показывают, на сколько внутренняя оценка производства j-го вида продукции превосходит его внешнюю оценку (дополнительная двойственная переменная положительная) или, что производство данной продукции оправданно по отношению к затраченным ресурсам (дополнительная двойственная переменная равна нулю);
4) суммарная оценка использованных в производстве ресурсов Lmin совпадает с полученным от реализации продукции доходом Fmax, т.е. Lmin=Fmax=38/3 тыс. грн.
Пример 3.11
Рассмотрим двойственную задачу для задачи о рационе (см. примеры 2.3 и 3.9):
L = 60y1 + 50y2 → max
y1 + 2y2≤ 19
3y1 + 4y2 ≤ 24
4y1 + 2y2 ≤ 25
yj ≥ 0, j=1,2
Найдем оптимальное решение пары двойственных задач, решив двойственную задачу симплекс – методом (она соответствует виду ЗЛП, для которой описан алгоритм симплексного метода).
Каноническая форма:
L = 60y1 + 50y2 → max
y1 + 2y2 + у3 =19
3y1 + 4y2 +у4 =24
4y1 + 2y2 +у5 =25
yj ≥ 0;
Решение оформим в виде последовательности симплекс-таблиц.
i | Базис | Сб | Р0 | 60 | 50 | 0 | 0 | 0 |
Y1 | Y2 | Y3 | Y4 | Y5 | ||||
Y3 | ||||||||
Y4 | ||||||||
Y5 | ||||||||
-60 | -50 | |||||||
Y3 | 51/4 | 3/2 | -1/4 | |||||
Y4 | 21/4 | 5/2 | -3/4 | |||||
Y1 | 25/4 | ½ | ¼ | |||||
-20 | ||||||||
Y3 | 48/5 | -3/5 | 1/5 | |||||
Y4 | 21/10 | 2/5 | -3/10 | |||||
Y1 | 26/5 | -1/5 | 2/5 | |||||
х*4 | х*5 | х*1 | х*2 | х*3 |
Так как все yj ≥ 0; , то план оптимален:
Y* = (26/5; 0; 0; 21/10; 45/5; 0; 0) , Lmax = 417.
Согласно приложению к теореме 3.3. имеем: Х*=(0;8;9;0;0); Fmin=Lmax=417.
Таким образом, рекомендуется составить кормовую смесь из 8 и 9 кг кормов 2-го и 3-го видов (х*2 = 8, х*3 = 9) соответственно Их использование оправдано (у*4 = у*5 = 0). Первый вид корма использовать не целесообразно (х*1=0). Возможный убыток при включении 1 кг корма 1-го вида в кормовую смесь составит 48/5 грн. (у*3 = 48/5).
Составленная кормовая смесь обеспечит животным получение необходимого количества питательных веществ А и В, а именно 50 и 60 единиц соответственно. Причем, питательное вещество А ценнее, чем вещество В (у*1=25/6 > у*2 = 21/10). При этом стоимость кормовой смеси будет минимальной и составит 417 грн.