5 различных задач по программированию (стр. 2 из 3)
b`i=bi - (ais/ars)*br
b`r=br/ars
s=1, r=2
a`11=0
a`13=4-2/7*7=2
a`14=0+2/7 *1=2/7
a`15=1
a`16= -5/14
a`17=0-2/7*1=-2/7
a`21=1
a`23= -1/2
a`24=4/7
a`25=0
a`26=2/7
a`27= -1/14
a`31= a31/a32=0
a`32=1
a`33= a33/a32=1
a`34= -1/7
a`35= 0
a`36=-1/14
a`37=1/7
a`41= 0
a`42= -14+2*7=0
a`43= 4
a`44=3
a`45=0
a`46=8
a`47=2
a`12=a`22=0
b`1=29-84/7*2=5
b`2=37-84/7*1/2=31
b`3=84/7=12
Эта система преобразуется к виду
2 x3 + 2/7 x4 + x5 – 5/14 x6 – 2/7 x7 = 5
x1 - Ѕ x3 +
x4 + 2/7 x6 – 1/14 x7 = 31 (18)x2 + x3 - 1/7 x4 – 1/14 x6 + 1/7 x7 = 12
4 x3 + 3 x4 + 8 x6 + 2 x7 = 1500 - z
Первые три уравнения системы (18) представляют некоторый предпочитаемый эквивалент системы уравнений (5) и определяют базисное неотрицательное решение системы условий рассматриваемой задачи
x1=37, x2=0, x3=0, x4=0, x5=29, x6=0, x7=84 (19)
т.е. определяют производственную программу x1=37, x2=0, x3=0, x4=0 (20)
и остатки ресурсов:
первого вида х5=5
второго вида х6=0 (21)
третьего вида х7=0
Последнее уравнение системы (18) мы получаем, исключая х2. В последнем уравнении системы (18) среди коэффициентов при неизвестных в левой части уравнения нет ни одного отрицательного. Если из этого уравнения выразить функцию цели z через остальные неотрицательные переменные
z = 1500 - 4 x3 - 3 x4 - 8 x6 - 2x7 (22)
то становится совершенно очевидным (в силу того, что все xj³0), что прибыль будет наибольшей тогда, когда
x3=0, x4=0, x6=0, x7=0 (23)
Это означает, что производственная программа (20) является наилучшей и обеспечивает предприятию наибольшую прибыль zmax = 1500 (24)
Итак, организовав направленный перебор базисных неотрицательных решений системы условий задачи, мы пришли к оптимальной производственной программе и указали остатки ресурсов, а также максимальную прибыль.
Следует обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Например, коэффициент D3=4 при переменной х3 показывает, что если произвести одну единицу продукции третьего вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 4 единиц.
Воспользуемся тем, что в оптимальной производственной программе x3=0, x4=0. Предположим, что четвертую и третью продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:
 |
Следует при этом обратить внимание на то, что последовательное улучшение производственной программы (x1=0, x2=0) ® (x1=37, x2=0) ® (x1=31, x2=12) на графике означает движение от одной вершины многогранника допустимых решений к другой вершине по связывающей их стороне многоугольника.
ДВОЙСТВЕННАЯ ЗАДАЧА
Ранее мы рассмотрели конкретную линейную производственную задачу по выпуску четырех видов продукции с использованием трех видов ресурсов по заданным технологиям.
Теперь представим себе, что знакомый предприниматель П, занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у1 рублей за каждую единицу первого ресурса, у2 руб – второго, у3 руб – третьего. Возникает вопрос: при каких ценах у1, у2, у3 мы можем согласиться с предложением П.
Величины у1, у2, у3 принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.Напомним, что в нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид
Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 2 единицы ресурса первого вида, 4 единицы ресурса второго вида и 2 единицы третьего (элементы первого столбца матрицы). В ценах у1, у2, у3 наши затраты составят 2у1 + 4у2 + 2у3, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы продукции первого вида. На рынке за единицу первой продукции мы получили бы прибыль 36 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше 2у1 + 4у2 + 2у3 ³ 36.
Аналогично, для трех оставшихся видов продукции:
3у1 + 2у2 + 8у3³32
4у1 + 7у3³10
у1 + 2у2 ³13
Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить 103у1 + 148у2 + 158у3 рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у1, у2, у3, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.
Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок у(у1, y2, y3) минимизирующий общую оценку всех ресурсов f = 103у1 + 148у2 + 158у3 (1)
при условии, что по каждому виду продукции суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции
2у1 + 4у2 + 2у3 ³ 36
3у1 + 2у2 + 8у3³32 (2)
4у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) = 0x 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 = 03y1 + 2y2 + 8y3 - 32 = 0
Если же учесть, что первый ресурс был избыточным и, согласно той же теореме двойственности, ее двойственная оценка равна нулю у1=0,
то приходим к системе уравнений
4y2 + 2y3 - 36 = 02y2 + 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-1T
0.Задача состоит в том, чтобы найти вектор T (0, t2, t3), максимизирующий суммарный прирост прибыли W = 8t2 + 2t3 (1) при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)
(3)