Прикладная математика (стр. 4 из 14)

и решили перевести свободную переменную х₁ в число базисных, для чего, согласно (20)определили разрешающее уравнение и указали разрешающий элемент а₁₁=1.

Учитывая сказанное выше, теперь мы будем преобразовывать не систему (17), а всю вспомогательную систему (24), по формулам исключения. Эта система преобразуется к виду

x₁+ 2x₂ + 2x₃ + x₅- x₇ = 27

3x₂ -

x₃ -

x₅ + x₆ +

x₇ = 13 (25)

- x₂ -

x₃ + x₄ -

x₅ +

x₇ = 20

8x₂ + 7x₃ + 6x₅ + 4x₇ = 1972 - z

Первые три уравнения системы (25) представляют некоторый предпочитаемый эквивалент системы уравнений (11) и определяют базисное неотрицательное решение системы условий рассматриваемой задачи

x₁=27, x₂=0, x₃=0, x₄=20, x₅=0, x₆=13, x₇=0 (26)

т.е. определяют производственную программу

x₁=27, x₂=0, x₃=0, x₄=20 (27)

и остатки ресурсов:

первого вида х₅=0

второго вида х₆=13 (28)

третьего вида х₇=0

В последнем уравнении системы (25) среди коэффициентов при неизвестных в левой части уравнения нет ни одного отрицательного. Если из этого уравнения выразить функцию цели z через остальные неотрицательныепеременные

z = 1972 - 8х₂- 7х₃- 6х₅-4х₇(29)

то становится совершенно очевидным (в силу того, что все x_j³0), что прибыль будет наибольшей тогда, когда

x₂=0, x₃=0, x₅=0, x₇=0 (30)

Это означает, что производственная программа (27) является наилучшей и обеспечивает предприятию наибольшую прибыль

z_max = 1972 (31)

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

Остается заметить, что процесс решения обычно записывается в виде некоторой таблицы 1.

Таблица 1

36 14 25 50 0 0 0	Пояснения
	Базис	Н	x₁ x₂ x₃ x₄ x₅ x₆ x₇
0	х₅	208	4 3 4 5 1 0 0	z₀ = H
0	х₆	107	2 5 0 2 0 1 0
0	х₇	181	3 1 2 5 0 0 1	0
z₀ -z	0 - z	-36 -14 -25 -50 0 0 0
0	х₅	27	1 2 2 0 1 0 -1
0	х₆	173/5	4/5 23/5 -4/5 0 0 1 -2/5
50	х₄	181/5	3/5 1/5 2/5 1 0 0 1/5
z₀ -z	1810-z	-6 -4 -5 0 0 0 10
36	х₁	27	1 2 2 0 1 0 -1
0	х₆	13	0 3 -12/5 0 -4/5 1 2/5	все D_j³0
50	х₄	20	0 -1/5 -4/5 1 -3/5 0 4/5
z₀ -z	1972-z	0 8 7 0 6 0 4

где представлены расширенные матрицы вспомогательных систем уравнений (22) ® (24) ® (25). Эти таблицы принято называть симплексными.

Следует обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Например, коэффициент D₃=7 при переменной х₃ показывает, что если произвести одну единицу продукции третьего вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц.

В заключение заметим, что в рассматриваемом простейшем примере линейной производственной задачи возможна самопроверка результата.

Воспользуемся тем, что в оптимальной производственной программе х₂=0, х₃=0. Предположим, что вторую и третью продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

Студенту не составит труда решить эту задачу графически и убедиться, что результаты совпадают.

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

(x₁=0, x₄=0) ® (x₁=0, x₄=

) ® (x₁=27, x₄=20)

на графике означает движение от одной вершины многогранника допустимых решений к другой вершине по связывающей их стороне многоугольника (в случае трех переменных это будет "езда" по ребрам многогранника допустимых решений от одной вершины к другой до достижения оптимальной вершины).

§5. Двойственная задача

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

Теперь представим себе, что возникла новая ситуация. Знакомый предприниматель П (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у₁ рублей за каждую единицу первого ресурса, у₂ руб – второго, у₃ руб – третьего. Возникает вопрос: при каких ценах у₁, у₂, у₃ мы можем согласиться с предложением П.

Величины у₁, у₂, у₃ принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.

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

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 4 единицы ресурса первого вида, 2 единицы ресурса второго вида и 3 единицы третьего (элементы первого столбца матрицы). В ценах у₁, у₂, у₃ наши затраты составят 4у₁+ 2у₂+ 3у₃, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 36 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше

4у₁+ 2у₂+ 3у₃³ 36.

Аналогично, во втором столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции второго вида. В ценах П эти затраты составят 3у₁+ 5у₂+ у₃, а на рынке за единицу продукции второго вида мы получили бы прибыль 14 рублей. Поэтому перед предпринимателем П мы ставим условие

3у₁+ 5у₂+ у₃³ 14

и т.д. по всем видам продукции.

Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить 208у₁+ 107у₂+ 181у₃ рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у₁, у₂, у₃, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.

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