4.9.7. Примеры

Пример 4.2. Для иллюстрации работы алгоритма применим его к задаче планирования, решенной графически в разд. 4.6.

Исходная модель L=7x1+5x2→max, 1) 2x1+3x219, 2) 2x1+x213, 3) 3x212, 4) 3x117, 5) x10, 6) x20.

Каноническая модель L=7x1+5x2→max, 2x1+3x2+x3=19, 2x1+x2+ x4=13, 3x2+x5=12, 3x1+x6=17, xj0.

Исходная модель соответствует первому случаю построения начального базисного решения (см. разд. 4.9.4). Следовательно, базисными переменными в начальном решении будут дополнительные переменные x₃, x₄, x₅ и x₆, а базисными векторами  А₃, А₄, А₅ и А₆. Очевидно, что такое базисное решение является допустимым (опорным планом), а в геометрическом представлении это вершина в начале координат.

Имея начальное решение, заполняем начальную симплекс-таблицу. В столбцы A₁ - A₆ заносятся коэффициенты при переменных x₁-x₆ в канонической модели, а в A₀ – свободные члены. Так как C₃, C₄, C₅ и C₆ равны нулю, то согласно (4.14) и все z_j=0. Следовательно, в этом случае Δ_j= z_j  C_j = C_j.

Таблица 0			0	7	5	0	0	0	0	
i	Csi	Баз.	A0	A1	A2	A3	A4	A5	A6
1	0	A3	19	2	3	1	0	0	0	19/2
2	0	A4	13	2	1	0	1	0	0	13/2
3	0	A5	12	0	3	0	0	1	0	--
4	0	A6	17	3	0	0	0	0	1	17/3
5	Δj		0	7	5	0	0	0	0
6	zj		0	0	0	0	0	0	0

Анализируем таблицу. Признак оптимальности не выполняется и при этом в столбцах с отрицательными Δ_j есть положительные элементы, значит, решение можно улучшить. По минимальному значению Δ_j определяем направляющий столбец - A₁. Вычисляем  делением элементов столбца A₀ на положительные элементы направляющего столбца. По минимальному значению  находим направляющую строку – строка 2. Направляющий столбец и направляющая строка выделены в таблице серым цветом. Таким образом, из базиса выходит вектор A₆ и на его место встает A₁. Аналогичная смена происходит в базисном решении: x₁ заменяет x₆.

Переходим к вычислению элементов новой таблицы. Новые значения в строке 4 получаем делением элементов этой строки в начальной таблице на направляющий элемент. Остальные элементы в небазисных столбцах, столбце A₀ и новые значения Δ_j вычисляются по правилу прямоугольника. Для примера в начальной таблице показаны 2 прямоугольника, которые построены на элементах ₁₆ и Δ₂. Они позволяют вычислить новые значения этих элементов:

₁₆ = 0  (2*1)/3= 2/3; Δ₂= 5  (7*0)/3= 5.

В результате получаем симплекс-таблицу 1.

Таблица 1			0	7	5	0	0	0	0	
i	Csi	Баз.	A0	A1	A2	A3	A4	A5	A6
1	0	A3	23/3	0	3	1	0	0	2/3	23/9
2	0	A4	5/3	0	1	0	1	0	2/3	5/3
3	0	A5	12	0	3	0	0	1	0	4
4	7	A1	17/3	1	0	0	0	0	1/3	--
5	Δj		119/3	0	5	0	0	0	7/3
6	zj		119/3	7	0	0	0	0	7/3

В ней также показаны вспомогательные строки (верхняя и нижняя) и вспомогательный столбец C_si. Они предназначены для контроля вычислений оценок (непосредственно по формулам (4.14) и (4.15)), а значит, и всей таблицы. Легко проверить, что в нашем случае эти формулы дают те же значения оценок.

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

Таблица 2			0	7	5	0	0	0	0	
i	Csi	Баз.	A0	A1	A2	A3	A4	A5	A6
1	0	A3	8/3	0	0	1	3	0	4/3	2
2	5	A2	5/3	0	1	0	1	0	2/3	--
3	0	A5	7	0	0	0	3	1	2	7/2
4	7	A1	17/3	1	0	0	0	0	1/3	17
5	Δj		48	0	0	0	5	0	1
6	zj		48	7	5	0	5	0	1

Так как оптимальное решение не достигнуто, проводим 3-ю итерацию, результаты которой представлены в табл. 3.

В этой таблице нет отрицательных оценок, что свидетельствует о достижении оптимального решения. Максимальная прибыль составляет L^*=50 при значениях переменных х^*₁ =5, х^*₂ =3, х^*₃ =х^*₄ =0, х^*₅ =3, х^*₆ =2, что полностью совпадает с результатами графического решения в разд. 4.6.

Таблица 3			0	7	5	0	0	0	0
i	Csi	Баз.	A0	A1	A2	A3	A4	A5	A6
1	0	A6	2	0	0	3/4	9/4	0	1
2	5	A2	3	0	1	1/2	1/2	0	0
3	0	A5	3	0	0	3/2	3/2	1	0
4	7	A1	5	1	0	1/4	3/4	0	0
5	Δj		50	0	0	3/4	11/4	0	0
6	zj		50	7	5	3/4	11/4	0	0

Пример 4.3. Рассмотрим задачу с разными видами ограничений и покажем только отличие от предыдущего примера.

Исходная модель L= 4x1 - x2→max, 1) 3x1+2x2  10, 2) 2x1+x2 8, 3) x1 - 3x2 =12, 4) x10, 5) x20.

Каноническая модель L= 4x1 - x2→max, 3x1+2x2+x3 = 10, 2x1+x2 - x4 = 8, x1 - 3x2 = 12, xj0.

Для построения начального базисного решения по 4-му варианту введем искусственные переменные x₅ и x₆. Тогда модель примет вид

L= 4x₁ - x₂→max,

3x₁+2x₂+x₃ = 10,

2x₁+x₂ - x₄+x₅ = 8,

x₁ - 3x₂+x₆ = 12,

x_j0.

Из нее получаем искусственное (недопустимое) базисное решение: x₃=10, x₅ = 8, x₆ = 12 (остальные переменные равны нулю). Соответственно базис состоит из одноименных векторов условий.

Далее можно выбрать один из способов решения:

1. решение в один этап;

2. решение в два этапа.

В первом случае критерий модифицируется введением искусственных переменных с большим весом: L^’= 4x₁ - x₂ - M(x₅+x₆). Вместо символа большого числаM можно взять конкретное значение, например положить M= 100, что много больше С₁ = 4. Дальше решение проводится согласно описанному алгоритму.

При использовании второго варианта на первом этапе решается задача минимизации искусственного критерия: L_и= x₅ + x₆→min. Если оптимальное значение этого критерия окажется отличным от нуля, исходная задача неразрешима из-за противоречивости условий. Нулевое значениебудет свидетельствовать о достижении допустимого базисного решения, которое принимается за начальное для второго этапа. На нем решается задача по исходному критериюL. При этом в последней таблице первого этапа относительные оценки по критериюL_и заменяются оценками по критерию L. Они вычисляются так же, как в начальной таблице.