Примечание

В случае, когда среди векторов Р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

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 грн.