Формулировка линейной производственной задачи

Представим, что другое предприятие, производящее другие виды продукции  по другим технологиям, но с использованием трех таких же видов ресурсов, которые имеются у нас, предлагает нам «уступить» имеющиеся у нас ресурсы по «договорным» ценам. Возникает вопрос: при каких предложенных ценах мы можем согласиться с таким предложением.

 

Технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С известны:

                                3     0     3     3               186

                     A =     2     3     1     1     B =    102       C = (38  12  28  21)

                                  4     3     2     2               196 

а) Обозначим стоимость  единицы каждого вида ресурса  через вектор У (у1, у2, у3,) значение компонент которого прямо зависит от условий, в которых действует наше предприятие.

 

б) Для производства единицы  продукции первого вида  мы должны затратить, как видно из матрицы  затрат А, 3, 2 и 4 единиц 1-го, 2-го и 3-го видов  ресурсов соответственно (элементы первого  столбца матрицы).

В ценах  у1, у2, у3 наши затраты на производство одной единицы первого вида продукции составят: 3у1 + 2у2 + 4у3, т.е. столько нам готово заплатить другое предприятие за все ресурсы, идущие на производство первого вида продукции. На рынке за единицу первого вида продукции мы получили бы прибыль в размере 38 денежных единиц.

Следовательно, мы можем  согласиться с предложением «уступить» ресурсы, идущие на производство первого  вида продукции, только в том случае, если нам заплатят не меньше 38 денежных единиц. Математически это можно выразить неравенством:

3у1 + 2у2 + 4у3 ≥ 38

Аналогичное условие  «уступки» ресурсов мы поставим и  по другим видам продукции:

          3у2 + 3у3 ≥ 12

 

3у1  +  у2 + 2у3 ≥ 28

 

3у1 +   у2 + 2у3 ≥ 21

 

в) Выразим через введенные  переменные у1, у2, у3 общую стоимость всех имеющихся ресурсов, которую нам должны заплатить:

 

F = 186у1 + 102у2 + 196у3 денежных единиц.

 

При поставленных нами условиях покупающее ресурсы предприятие  будет искать такие значения у1, у2, у3, чтобы общая стоимость всех ресурсов была как можно меньше.

 

Таким образом, проблема определения  расчетных оценок ресурсов приводит к задаче линейного программирования:

 

Найти вектор двойственных оценок ресурсов:                              У (у1, у2, у3, у4),

 

минимизирующий общую оценку всех ресурсов                         F = 186у1 + 102у2 + 196у3 → min,

при условии, что по каждому виду продукции                              3у1 + 2у2 + 4у3 ≥ 38

суммарная оценка всех ресурсов, затрачиваемых на                               3у2 + 3у3 ≥ 12

производство единицы продукции, не меньше                              3у1  +  у2 + 2у3 ≥ 28

прибыли, получаемой от реализации единицы                              3у1 +   у2 + 2у3 ≥ 21

этой продукции,

 

причем оценки ресурсов не могут  быть отрицательными             у1 ≥ 0, у2 ≥ 0, у3 ≥ 0

 

Полученная задача является двойственной к основной задаче линейного программирования.

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

у1 (3х1           + 3х3 + 3х4 – 186) = 0            у2 (2х1 + 3х2   +  х3    +  х4 - 102) = 0            у3 (4х1 + 3х2 +  2х3 + 2х4 - 196) = 0

х1 (3у1 + 2у2 + 4у3 - 38) = 0 х2 (           3у2 + 3у3 - 12) = 0 х3 (3у1  +  у2 + 2у3 - 28) = 0 х4 (3у1 +   у2 + 2у3 - 21) = 0

Другими словами, дефицитный ресурс, полностью используемый по оптимальному плану производства, имеет положительную оценку, а ресурс, являющийся избыточным и используемый не полностью, имеет нулевую оценку.

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

 

Поскольку оптимальная производственная программа Х*(х1*, х2*,х3*, х4*) нам известна (см. п. 1.4.): х1* = 36, х2* = 0, х3* = 26, х4* = 0, подставим значения известных нам переменных в уравнения:

у1 (3 * 36 + 3 * 26 - 186) = 0            у2 (2 * 36      +  26 - 102) = 0            у3 (4 * 36 + 2 * 26 - 196) = 0

36 (3у1 + 2у2 + 4у3 - 38) = 0   0 (           3у2 + 3у3 - 12) = 0 26 (3у1  +  у2 + 2у3 - 28) = 0   0 (3у1 +   у2 + 2у3 - 21) = 0

ИЛИ

у1 (186 - 186) = 0            у2 ( 98 - 102)  = 0            у3 (196 - 196) = 0

36 (3у1 + 2у2 + 4у3 - 38) = 0   0 (           3у2 + 3у3 - 12) = 0 26 (3у1  +  у2 + 2у3 - 28) = 0   0 (3у1 +   у2 + 2у3 - 21) = 0

В первой группе уравнений  второе уравнение у2( 98 - 102)  = 0 означает, что при выполнении оптимальной производственной программы второй ресурс расходуется не полностью (98 единиц из 102), следовательно, двойственная оценка второго ресурса равна нулю: у2* = 0

Остальные (первый и третий) ресурсы расходуются полностью и являются дефицитными, следовательно, у1*, у3* > 0

 

Первое и третье уравнения второй группы означают, что поскольку продукции  первого и третьего вида входят в  оптимальную производственную программу (х1* = 36, х3* = 26), то суммарная двойственная оценка ресурсов, расходуемых на производство первого и третьего видов продукции соответственно, должна быть равна цене единицы этого вида продукции.

Получаем:                                          

у2* = 0 

3у1 + 2у2 + 4у3 = 38

3у1  +  у2 + 2у3 = 28

Решаем полученную систему уравнений

у2* = 0  3у1 + 4у3 = 38 3у1 + 2у3 = 28

у2* = 0  2у3 = 10 3у1 + 2у3 = 28

у2* = 0  у3* = 5 3у1 = 18

у2* = 0  у3* = 5 у1* = 6

Таким образом, двойственные оценки ресурсов у1* = 6, у2* = 0, у3* = 5

 

При этом общая оценка всех ресурсов равна

F*(min) = 186у1* + 102у2* + 196у3* = 186 * 6 + 196 * 5 = 1116 + 980 = 2096 денежных единиц.

Экономически смысл двойственных оценок ресурсов у1* = 6, у2* = 0, у3* = 5 показывает, что добавление одной единицы 1-го (2-го, 3-го) ресурса обеспечит прирост прибыли на 6 (0, 5) денежных единиц.

 

Из второй основной теоремы двойственности следует, что технология, применяемая  с ненулевой интенсивностью, имеет  нулевую оценку, а технология, применяемая  с нулевой интенсивностью, имеет  положительную оценку.

Оценка 1-ой технологии: ∆1 = 3у1* + 2у2* + 4у3* - 38

                                           ∆1 = 3*6 + 2*0 + 4*5 – 38

                                               ∆1 = 0

Действительно, 1-ая технология применяется (производство продукции  первого вида входит в оптимальную  производственную программу).

Оценка 2-ой технологии: ∆2 = 3у2* + 3у3* - 12

                                           ∆2 = 3*0 + 3*5 – 12

                                               ∆2 = 3

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

Оценка 3-ей технологии: ∆3 =  3у1*  +  у2* + 2у3* - 28

                                           ∆3 = 3*6 + 0 + 2*5 – 28

                                               ∆3 = 0

3-я технология применяется.

Оценка 4-ой технологии: ∆4 = 3у1* +   у2* + 2у3* - 21

                                           ∆4 = 3*6 + 0 + 2*5 – 21

                                           ∆4 = 7

Если произвести одну единицу 4-го вида продукции, то прибыль  уменьшится на 7 денежных единиц.

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

 

2.2. Задача о «расшивке  узких мест производства»

 

Сформулируем задачу о  расшивке «узких мест производства»  и составим ее математическую модель.

Решив задачу о рациональном использовании  имеющихся ресурсов, мы выяснили, что  первый и третий виды ресурсов расходуются полностью, т.е. образуют «узкие места производства». Будем расширять производство за счет увеличения объема дефицитных ресурсов.

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

Пусть T (t1, t2, t3) – вектор дополнительных объемов ресурсов, каждая компонента которого обозначает искомое дополнительное количество соответствующего вида ресурса. Поскольку дополнительно мы заказываем только дефицитные ресурсы, а второй ресурс является избыточным, то t2* = 0

Прирост прибыли, приходящийся на дополнительное количество какого-либо вида ресурса, равен произведению дополнительного количества этого ресурса на его двойственную оценку (напомним, что двойственные оценки ресурсов найдены решением предыдущей задачи), а суммарный прирост прибыли от увеличения количества ресурсов будет равен:

W = 6t1 + 0t2 + 5t3 = 6t1 + 5t3

 

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

H + Q^-1T ≥ 0,

 

где Q^-1  - обращенный базис, т.е. матрица, которая содержится в последней симплексной таблице на месте единичной матрицы в первой симплексной таблице, Н – вектор оптимальных значений базисных переменных в последней симплексной таблице, а Т – искомый вектор дополнительных объемов ресурсов.

Выполнение данного  неравенства обеспечивает также  устойчивость (неизменность) двойственных оценок ресурсов, которая необходима, поскольку в решении задачи о  «расшивке узких мест производства»  используются ранее найденные двойственные оценки ресурсов.

В данном случае также  должно выполняться условие, что  дополнительно можно получить от поставщиков не более одной трети  первоначально выделенного объема ресурса любого вида:

 

T ≤ 1/3 B

Математическая  модель задачи будет выглядеть следующим образом:

 

Найти вектор дополнительных объемов ресурсов   T (t1, 0, t3),

 

максимизирующий суммарный  прирост прибыли   W = 6t1 + 5t3  → max,

 

при условии сохранения структуры

производственной программы

и двойственных оценок ресурсов H + Q^-1T ≥ 0:           

26            2/3     0     -1/2             t1      

4      +      0        1     -1/2     *      0       ≥    0

36           -1/3     0      1/2             t3

                                                                                                             ИЛИ        

- 2/3 t1 + 1/2t3 ≤ 26

Область устойчивости                                              1/2t3 ≤  4

 двойственных оценок  ресурсов                              1/3t1 – 1/2t3  ≤ 36

где по дополнительному  условию задачи                t1 ≤ 186/3

                                                                                      t3 ≤ 196/3

 

и по смыслу задачи                                                     t1 ≥ 0, t3 ≥ 0  

Приходим к задаче линейного программирования с двумя переменными.

 

 Решим задачу  о «расшивке узких мест» графически.

Построим систему координат, где на горизонтальной оси будем  откладывать значения t1, а на вертикальной – t3, причем нас интересует только правая верхняя полуплоскость данной системы, поскольку по условию задачи t1 ≥ 0, t3 ≥ 0.

Каждое линейное неравенство-ограничение  на графике определяет полуплоскость  допустимых значений переменных этого  неравенства вместе с ограничивающей данную полуплоскость прямой, множество  точек которой является решением соответствующего неравенству линейного уравнения: