левой части уравнения нет ни одного отрицательного. Если из этого уравнения

выразить функцию цели z через остальные неотрицательные переменные

z = 1972 - 8х2 - 7х3 - 6х5 - 4х7 (29)

то становится совершенно очевидным (в силу того, что все xj³0),

что прибыль будет наибольшей тогда, когда

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
0	х5	208	4 3 4 5 1 0 0	z0 = H
0	х6	107	2 5 0 2 0 1 0
0	х7	181	3 1 2 5 0 0 1	0
	z0 -z	0 - z	-36 -14 -25 -50 0 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	все Dj ³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). Эти таблицы принято называть симплексными.

Следует обратить внимание на экономический смысл элементов последней строки

последней симплексной таблицы. Например, коэффициент D3=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 ³ 36

3y1 + 5y2 + y3 ³ 14

4y1 + 2y3 ³ 25

5y1 + 2y2 + 5y3 ³ 50

причем оценки ресурсов не могут быть отрицательными

y10, y20, y30. (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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14