А. Кофман и Р. Фор. Займемся исследованием операций (стр. 28 )

Если новая функция прибыли имеет вид

F = 15x1 + 12x2 + 14x3,

то какие значения нужно придать х1, х2, х3, чтобы F была максимальной?

Графический метод, использованный ранее для рис. 13.1, привел бы к представлению в трех измерениях (рис. 13.2). На таком рисунке становится уже неудобно определять ту вершину выпуклого многогранника, представляющего ограничения (∆), которая соответствует максимуму F. В этих условиях мы будем использовать другой метод, названный симплекс-методом, принадлежащий американскому математику Джорджу Данцигу.

Для начала заметим, что ограничения Δ3, Δ4, которые неявно удовлетворяются благодаря Δ1 и Δ2, можно отбросить; действительно, если

,

то тем более справедливо[68] неравенство

.

Итак, задача сводится к следующему:

максимизировать F = 15x1 + 12х2 + 14x3,

принимая в расчет более сильные ограничения:

Обозначим через x4, x5, x6 разности между левыми частями наших трех неравенств и их свободными членами[69]. Теперь можно заменить эти неравенства уравнениями:

Очевидное, но не представляющее интереса решение будет следующим:

х1 = х2 = х3 = 0,

т. е. x4 = 100, x5 = 100, x6 = 100, F = 0.

Это означает, что производить ничего не нужно (решение, годное только на период ежегодного закрытия на время отпусков!).

Однако при взгляде на рис. 13.2 ясно по аналогии с рис. 13.1, начерченным в плоскости, что оптимальное решение, если оно существует, должно находиться в одной из вершин выпуклого многогранника OABCDEFG. Любая из вершин дает решение, в котором три переменные из шести от x1 до x6 равны нулю. Решение х1 = х2 = х3 = 0 дает вершина Oмногогранника. Теперь мы перейдем от этой начальной вершины к соседней вершине, увеличивая значение F, если это возможно.

Выбираем переменную, которая входит в F с самым большим положительным коэффициентом, например переменную x1.

Рис. 13.2

Путем подстановки, строка за строкой, мы имеем возможность оставить только один ненулевой коэффициент в столбце х1 и исключить х1 из F; но куда поместить единственный коэффициент при х1, который не будет нулем?

Данциг показал, что для этого нужно сравнить следующие отношения[70]:

1,

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

В нашем примере — это, которое соответствует строке 1. Это условие, которое Данциг установил в общем виде, позволяет изменить решение так, чтобы ни одна из переменных не стала отрицательной.

Умножим первую строку на 200, чтобы иметь х1 вместо :

.

Затем добавим эту строку, предварительно умноженную на , ко второй и, умноженную на, —к строке F; получим

Новое, улучшенное решение представляется следующим образом:

x2 = x3 = x4 = 0, x1 = 20 000, x5 = , x6 = 100;

при этом F = Мы находимся в вершине A (рис. 13.2).

Продолжим наши вычисления. В строке F имеется еще один положительный коэффициент — это коэффициент при переменной x2 (если бы таких коэффициентов было несколько, то мы выбрали бы наибольший из них).

В столбце x2 образуем отношения

;

таким образом, нужно выбрать строку 2, для которой имеем наименьшее положительное отношение/7. Строку 2 умножим на 900/7, затем добавим ее ко всем строкам, которые содержат x2, предварительно умножив их на подходящие числа, такие, чтобы в столбце, соответствующем x2, все коэффициенты стали бы нулями, за исключением коэффициента второй строки, который становится единицей.

Теперь мы имеем

Соответствующее решение будет

x3 = x4 = x5 = 0,

и F = франков; мы находимся в вершине B (рис. 13.2).

Можно утверждать, что F = франков составляет максимум; действительно, все коэффициенты F отрицательны и переход от точки B к любой соседней точке G, С или A уменьшил бы значение функции F. Это утверждение является общим: любой многогранник, который подобно изображенному выше построен, исходя из неравенств и неотрицательных значений x1, х2, х3, является выпуклым.

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

Таким образом, после вычисления мощностей и прибылей мы заключаем, что самовары производить не нужно, ибо реорганизация производства снизила бы прибыль с ,5 франков до франка; таким образом, предпочтительно оставить в стороне проект объединения этого нового производства с предыдущим в надежде, что это не окажет пагубного влияния на развитие отношений между Востоком и Западом.

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

Правила вычислений в симплекс-методе

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

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

Пусть, например, дана задача:

2х1 + 3х2 ≤ 8,

2х2 + 5х3 ≤ 10,

3х1 + 2х2 + 4х3 ≤ 15.

Целевая функция, подлежащая максимизации, имеет вид

F = 3x1 + 5x2 + 4x3;

при этом х1, x2, x3 должны быть, естественно, неотрицательны.

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

2х1 + 3х2 + x4 = 8,

2х2 + 5х3 + x5 = 10,

3х1 + 2х2 + 4х3 + x6 = 15,

сохраняя[71] целевую функцию F и условия неотрицательности в их первоначальной форме. Каждый вектор соответствующего пространства может быть представлен через некоторое число единичных векторов, называемых базисом; первые векторы, которые здесь приходят на ум, — это векторы осей х4, х5, х6.

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

Цена	Базисный столбец
Сi	Pi		P1	P2	P3	P4	P5	P6		P0
0	P4		2	3	0	1	0	0		8
0	P5		0	2	5	0	1	0		10
0	P6		3	2	4	0	0	1		15
	Cj		3	5	4	0	0	0
Решение			0	0	0	8	10	15

1)  На каждой итерации вычисляют для всех столбцов j, которые не входят в базис, следующие величины:

;

при этом xij обозначают элементы основной таблицы (строка i, столбец j).

Пример:

Теперь берут наибольшее положительное значение (по крайней мере одно из хij столбца Pj должно быть положительным) и выбирают для ввода в новый базис столбец Pj с соответствующим индексом. Обозначим через е индекс вводимого столбца. Очевидно, что если положительных или нулевых значений Δj нет, то получено оптимальное решение; если некоторые Δj равны нулю, а остальные отрицательны, то существуют эквивалентные решения. В нашем примере е=2.

2) Обозначая через Р0i элементы Р0, находят частные Р0i / xie, где xie — элементы вводимого столбца.

Выбирают наименьшее положительное частное Р0i / xie; пусть s — индекс i, который ему соответствует: он определяет индекс столбца, выводимого из базиса.

Пример:

.

3) Столбец, который выводится из базиса, содержит нули и единицу; назовем ведущим элементом столбца, вводимого в базис, тот элемент этого столбца, который находится в той же строке, что и единица выводимого из базиса столбца; далее

а) делят все элементы определенной строки на ведущий элемент;

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

Пример. Здесь ведущий элемент столбца Р2, соответствующий единице столбца Р4, есть 3. Следовательно, первая строка таблицы принимает вид

.

Затем нужно вычесть дважды элемент 1 из элемента 2 во второй строке столбца P2, чтобы получить 0, и дважды вычесть элемент 1 из элемента 2 в третьей строке столбца P2, чтобы получить 0.

Следовательно, вторая и третья строки получены вычитанием из их первоначальных элементов соответствующих элементов новой первой строки, умноженных на —2.

Цена	Базисный столбец
Сi	Pi		P1	P2	P3	P4	P5	P6		P0
5	P2		2/3	1	0	1/3	0	0		8/3
0	P5		-4/3	0	5	-2/3	1	0		14/3
0	P6		5/3	0	4	-2/3	0	1		29/3
	Cj		3	5	4	0	0	0
Решение			0	8/3	0	0	14/3	29/3	F=40/3