Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений (х1, х2, х3, х4) и (y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий

x 1 (2у1 + у2 + 3у3 - 34) = 0 y1 (2x1 + 2x3 + 3x4 - 142) = 0

x 2 ( 5у2 + 4у3- 20) = 0 y2 ( x1 +5x2 + 4x3 + 2x4 - 100) = 0

x 3 (2у1 + 4у2 - 8) = 0 y3 (3x1 +4x2 + x4- 122) = 0 .

x 4 (3у1 + 2у2 + у3 - 23) = 0

Ранее было найдено, что в решении исходной задачи х1>0, x4>0. Поэтому

2y1 + y2 + 3y3 - 34 = 0

3y1 + 2y2 + y3 - 23 = 0

Если же учесть, что второй ресурс был избыточным и, согласно той же теореме двойственности, ее двойственная оценка равна нулю у2=0,

то приходим к системе уравнений

2y1 + 3y3 - 34 = 0

3y1 + y3 - 23 = 0

откуда следует у1=5, у3=8.

Таким образом, получили двойственные оценки ресурсов у1=5; у2=0; у3=8, (4)

причем общая оценка всех ресурсов равна 1686.

Заметим, что решение (4) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка третьего ресурса у3=8 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли в 8 единицы.

ЗАДАЧА О "РАСШИВКЕ УЗКИХ МЕСТ ПРОИЗВОДСТВА"

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, т.е. образуют ²узкие места производства². Будем их заказывать дополнительно. Пусть T(t1,t2,t3)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться услови

H + Q-1T 0.

Задача состоит в том, чтобы найти вектор T (t1, 0, t3), максимизирующий суммарный прирост прибыли W = 5t1 + 8t3 (1) при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)

(2)

предполагая, что можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида (3)

причем по смыслу задачи t1 0, t3 0. (4)

Переписав неравенства (2) и (3) в виде:

(5)

из условия (3) следует t1£142/3, t3£122/3 (6)

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. 2.

I.) -3/7t1+2/7t3= 26

II.) 5/7t1-1/7t3= 16

III.) 1/7t1-3/7t3 = 32

M (458/15, 122/3)

Программа ²расшивки² имеет вид

t1=458/15, t2=0, t3=122/3 и прирост прибыли составит 5*458/15+8*122/3=478.

Сводка результатов приведена в таблице:

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

Однородный продукт, сосредоточенный в 3 пунктах производства (хранения) в количествах 80; 60; 30 единиц, необходимо распределить между 4 пунктами потребления, которым необходимо соответственно 34; 40; 38; 53 единиц. Стоимость перевозки единицы продукта из пункта отправления в пункт назначения известна для всех маршрутов и равна

С = .

Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Для решения транспортной задачи чаще всего применяется метод потенциалов.

Общий объем производства åаi =80+60+30=170 больше, чем требуется всем потребителям åbi = 34+40+38+53 =165, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 170-165 = 5 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.