Шпаргалка: 5 различных задач по программированию

Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить 103у1 + 148у2 + 158у3 рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у1 , у2 , у3 , чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.

Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок у1 , y2 , y3 ) минимизирующий общую оценку всех ресурсов f = 103у1 + 148у2 + 158у3 (1)

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

1 + 4у2 + 2у3 ³ 36

1 + 2у2 + 8у3 ³32 (2)

1 + 7у3 ³10

у1 + 2у2 ³13

причем оценки ресурсов не могут быть отрицательными y1 0, y2 0, y3 0. (3)

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

x 1 (2у1 + 4у2 + 2у3 - 36) = 0 y1 (2x1 +3x2 + 4x3 + x4 - 103) = 0

x 2 (3у1 + 2у2 + 8у3 - 32) = 0 y2 (4x1 +2x2 + 2x4 - 148) = 0

x 3 (4у1 + 7у3 - 10) = 0 y3 (2x1 +8x2 + 7x3 - 158) = 0 .

x 4 1 + 2у2 - 13) = 0

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

2y1 + 4y2 + 2y3 - 36 = 0

3y1 + 2y2 + 8y3 - 32 = 0

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

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

4y2 + 2y3 - 36 = 0

2y2 + 8y3 - 32 = 0

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

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

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

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

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

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

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

(2)

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

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

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

К-во Просмотров: 1239
Бесплатно скачать Шпаргалка: 5 различных задач по программированию