Прикладная математика
z = 1972 - 8х2 - 7х3 - 6х5 - 4х7 (29)
то становится совершенно очевидным (в силу того, что все xj0), что прибыль будет наибольшей тогда, когда
x2=0, x3=0, x5=0, x7=0 (30)
Это означает, что производственная программа (27) является наилучшей и обеспечивает предприятию наибольшую прибыль
zmax = 1972 (31)
Итак, организовав направленный перебор базисных неотрицательных решений системы условий задачи, мы пришли к оптимальной производственной программе и указали остатки ресурсов, а также максимальную прибыль.
Остается заметить, что процесс решения обычно записывается в виде некоторой таблицы 1.
Т
14
аблица 1| 36 14 25 50 0 0 0 | Пояснения | |||
|
|
Базис | Н |
x1 x2 x3 x4 x5 x6 x7 |
|
|
|
х5 |
208 |
4 3 4 5 1 0 0 |
z0
=
|
| 0 |
х6 |
107 |
2 5 0 2 0 1 0 |
|
| 0 |
х7 |
181 |
3 1 2 5 0 0 1 |
|
|
z0 -z |
0 - z |
-36 -14 -25 -50 0 0 0 |
|
|
|
|
х5 |
27 |
1 2 2 0 1 0 -1 |
|
| 0 |
х6 |
173/5 |
4/5 23/5 -4/5 0 0 1 -2/5 |
|
| 50 |
х4 |
181/5 |
3/5 1/5 2/5 1 0 0 1/5 |
|
|
z0 -z |
1810-z |
-6 -4 -5 0 0 0 10 |
|
|
| 36 |
х1 |
27 |
1 2 2 0 1 0 -1 |
|
| 0 |
х6 |
13 |
0 3 -12/5 0 -4/5 1 2/5 |
все j 0 |
| 50 |
х4 |
20 |
0 -1/5 -4/5 1 -3/5 0 4/5 |
|
|
z0 -z |
1972-z |
0 8 7 0 6 0 4 |
где представлены расширенные матрицы вспомогательных систем уравнений (22) (24) (25). Эти таблицы принято называть симплексными.
Следует обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Например, коэффициент 3=7 при переменной х3 показывает, что если произвести одну единицу продукции третьего вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц.
В заключение заметим, что в рассматриваемом простейшем примере линейной производственной задачи возможна самопроверка результата.
Воспользуемся тем, что в оптимальной производственной программе х2=0, х3=0. Предположим, что вторую и третью продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

С
15
туденту не составит труда решить эту задачу графически и убедиться, что результаты совпадают.Следует при этом обратить внимание на то, что последовательное улучшение производственной программы
(x1=0,
x4=0)
(x1=0,
x4=
)
(x1=27,
x4=20)
на графике означает движение от одной вершины многогранника допустимых решений к другой вершине по связывающей их стороне многоугольника (в случае трех переменных это будет "езда" по ребрам многогранника допустимых решений от одной вершины к другой до достижения оптимальной вершины).
§5. Двойственная задача
Ранее мы рассмотрели конкретную линейную производственную задачу по выпуску четырех видов продукции с использованием трех видов ресурсов по заданным технологиям.
Теперь представим себе, что возникла новая ситуация. Знакомый предприниматель П (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у1 рублей за каждую единицу первого ресурса, у2 руб – второго, у3 руб – третьего. Возникает вопрос: при каких ценах у1, у2, у3 мы можем согласиться с предложением П.
Величины у1, у2, у3 принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.
Напомним, что в нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 4 единицы ресурса первого вида, 2 единицы ресурса второго вида и 3 единицы третьего (элементы первого столбца матрицы). В ценах у1, у2, у3 наши затраты составят 4у1 + 2у2 + 3у3, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 36 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше
4у1 + 2у2 + 3у3 36.
Аналогично, во втором столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции второго вида. В ценах П эти затраты составят 3у1 + 5у2 + у3, а на рынке за единицу продукции второго вида мы получили бы прибыль 14 рублей. Поэтому перед предпринимателем П мы ставим условие
3у1 + 5у2 + у3 14
и т.д. по всем видам продукции.
Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить 208у1 + 107у2 + 181у3 рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у1, у2, у3, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.
Т
16
аким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценоку(у1, y2, y3)
минимизирующий общую оценку всех ресурсов
f = 208y1 + 107y2 +181y3 (1)
при условии, что по каждому виду продукции суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции
(2)
4y1 + 2y2 + 3y3 363y1 + 5y2 + y3 14
4y1 + 2y3 25
5y1 + 2y2 + 5y3 50
причем оценки ресурсов не могут быть отрицательными
y1
0,
y2
0,
y3
0.
(3)
Решение
полученной
задачи легко
найти с помощью
второй основной
теоремы двойственности,
согласно которой
для оптимальных
решений
(х1,
х2, х3,
х4) и
(y1,
y2, y3)
пары двойственных
задач необходимо
и достаточно
выполнение
условий
![]()
![]()
x 1 (4y1 + 2y2 + 3y3 - 36) = 0 y1 (4x1 +3x2 + 4x3 + 5x4 - 208) = 0
x 2 (3y1 + 5y2 + y3 - 14) = 0 y2 (2x1 +5x2 + 2x4 - 107) = 0
x 3 (4y1 + 2y3 - 25) = 0 y3 (3x1 + x2 + 2x3 + 5x4 - 181) = 0 .
x 4(5y1 + 2y2 + 5y3 - 50) = 0
Ранее было найдено, что в решении исходной задачи х1>0, x4>0. Поэтому
![]()
4y1 + 2y2 + 3y3 - 36 = 0
5y1 + 2y2 + 5y3 - 50 = 0
Если же учесть, что второй ресурс был избыточным и, согласно той же теореме двойственности, ее двойственная оценка равна нулю
у2=0,
то приходим к системе уравнений
4
y1
+ 3y3
- 36 = 0
5y1 + 5y3 - 50 = 0
откуда следует
у1=6, у3=4.
Таким образом, получили двойственные оценки ресурсов
у1=6; у2=0; у3=4, (4)
причем общая оценка всех ресурсов равна 1972.
17
Заметим, что решение (4) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка третьего ресурса у3=4 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли в 4 единицы.§6. Задача о "расшивке узких мест производства"
При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, т.е. образуют узкие места производства. Будем их заказывать дополнительно. Пусть T(t1,t2,t3)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие
H + Q-1T
0.
Задача состоит в том, чтобы найти вектор
T (t1, 0, t3),
максимизирующий суммарный прирост прибыли
W = 6t1 + 4t3 (1)
при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)
(2)
предполагая, что можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида
(3)
причем по смыслу задачи
t1
0, t3
0. (4)
П
ереписав
неравенства
(2) и (3) в виде:
(6)
(5)


приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).
Эту задачу легко решить графически: см. рис. 1. Программа расшивки имеет вид
t1=
,
t2=0, t3=![]()
и
18
прирост прибыли составит 519Сводка результатов приведена в таблице
Таблица 1
|
сj |
36 |
14 |
25 |
50 |
b |
x4+i |
yi |
ti |
|
4 |
3 |
4 |
5 |
208 |
0 |
6 |
46 5/12 |
|
|
aij |
2 |
5 |
0 |
2 |
107 |
13 |
0 |
0 |
|
3 |
1 |
2 |
5 |
181 |
0 |
4 |
60 1/3 |
|
|
xj |
27 |
0 |
0 |
20 |
1972 |
519 2/3 |
||
|
j |
0 |
8 |
7 |
0 |
§7. Транспортная задача линейного программирования
Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в m пунктах производства (хранения) в количествах а1, а2,..., аm единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно b1, b2,..., bn единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна сij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.
Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления
(1)
математическая модель транспортной задачи будет выглядеть так:
найти план перевозок
0
H
0
0