Иллюстрация процесса поиска решения

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

Дано: ЗЛП в виде алгебраической модели системы уравнений ОДР:

– общее условие допустимости решений, где при x₁=x₂=0 имеем:

x₁=x₂=0; x₃=320; x₄=200; x₅=280; x₆=–100;

w =3820.

Согласно условиям, т.к. x₆<0 (равно –100), то решение в точке (0,0) – начало координат на рис. 2.1 – не является допустимым. Точка (0, 0) не принадлежит области допустимых решений:

Для удобства анализа введем буквенное обозначение и представим рис. 2.1 в виде схемы рис. 2.2.

Далее рассуждения ведутся согласно принятой разметке ОДР в симплексах ОДР.

Итак, чтобы получить допустимое решение необходимо из точки «0» перейти в одну из точек симплекса { A_i; B_i; или C_i }, где .

Задача в примере невырожденная, т.к. во всех точках симплекса только две свободные переменные равны нулю, а именно (см. рис. 2.1):

A₁: x₂=x₆=0;

A₂: x₁=x₆=0

B₁: x₂=x₄=0

B₂: x₁=x₅=0

C₁: x₃=x₄=0

C₂: x₃=x₅=0

Переход из точки «0», где x₁=x₂ =0 в любую из точек { A₁; A₂; B₁; B₂ } соответствует правилу замены одной свободной переменной на одну базовую.

На рис. 2.2 показаны возможные пути перехода при решении задачи ЛП, соответствующие замене одной свободной переменной на одну базовую.

Очевидно, имеются четыре допустимых маршрута перехода из точки “0” в оптимальную точку (симплекс-вершину) :

1) ;

 

2)

3)

4) .

Из них самый короткий путь – через точки (0, В₁, ), самый долгий – через точки (0, А₂, В₂, С₂, ).

Заметим, что, если разметка конца стрелки совпадает с разметкой начала следующей по цепочке стрелки, то действует правило транзитивности, сокращающее путь на одну замену.

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

 

Алгебраическое решение

 

Рассмотрим логику алгебраического хода решения задачи, пролегающего через точки (0–А₁–В₁ – ).

Поиск опорного решения

Т.к. решение в точке “0” недопустимо из-за отрицательности значений x₆ = –100, напрашивается замена переменной x₁ на базовую переменную x₆ или x₂ на x₆.

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

уравнение x₆=x₁ +x₂–100 перерешим относительно x₁:

x₁=x₆ –x₂+100.

Теперь свободными переменными стали x₂ и x₆ (см. точку B₁).

При x₂=x₆=0 базовая переменная x₁=100, и условие x₁³0 выполняется.

В остальные уравнения подставим полученное значение x₁:

x₃=320– x₂–100– x₆– x₂=220– x₆;

x₄=200–100– x₆+ x₂=100– x₆+ x₂;

x₅=280– x₂;

w=3820–500–5 x₆+5 x₂–4 x₂=3320–5 x₆+ x₂Þ .

Опорное решение получено и равно:

x₆= x₂=0; x₁=100; x₃=220; x₄=100; x₅=280; w=3320.

Для минимизации w желательно значение x₆ сделать не только равным нулю, но и по возможности увеличить, поскольку значение –5x₆ вычитается из w=3820.

Вывод. Наличие отрицательных коэффициентов при свободных переменных в случае минимизации функции w указывает на неоптимальность данного решения.

Для анализа выпишем систему полученных уравнений:

x₁= x₆ – x₂+100;

x₃=220– x₃;

x₄=100– x₃+ x₂;

x₅=280– x₂;

w=3320– 5x₃+ x₂Þ .

Увеличение x₆ ограничено переменными x₃ и x₄, которые (при x₂=0) стремятся с ростом x₆ к уменьшению:

- при x₆=220 имеем x₃=0;

- при x₆=100 и x₂ =0 имеем x₄=0.

Следовательно, x₄ ограничивает рост x₆ раньше, чем x₃ (см. рис. 2.1). Путем замены x₄ на x₆ при x₂=0 критерий эффективности станет меньше на 500 усл. ед.: w(x₂;x₃)=3320–500=2820.

Переход из точки A₁®B₁ очевиден и из рис. 2.1.

По аналогии проведем замену переменных x₆ на x₄:

x₆= 100–x₄ + x₄;

x₁=200– x₄;

x₃=120– x₂+ x₄;

x₅=280– x₂;

w=2820 + 5x₄– 4x₂Þ .

Далее по аналогии, чем больше x₂, тем лучше решение. Однако x₃ ограничивает рост x₂ значением x₂=120. При этом получаем от замены x₂ на x₃ выигрыш w= – 4×120=480.

Проведем замену x₂ на x₃:

X₂= 120 + x₄ – x₃;

X₁=200– x₄;

X₅=160– x₄+ x₃;

x₃=220– x₃;

w=2380 + x₄+4 x₃=w_min..

Итак, решение достигнуто в точке x₃= x₄=0; x₁=200; x₂=180; x₅=160; x₆=220; w=2380.

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

 

2.3. Табличный вариант замены переменных

Замена переменных является типовой процедурой деятельности при решении задачи ЛП.

Рассмотрим процедуру замены на примере ограничений абстрактной системы уравнений, записанной в форме:

y1=b1+a11x1+a12x2; y1=b2+a21x1+a22x2; y1=b3+a31x1+a32x2; y1=b4+a41x1+a42x2; w=	x3=y1; x4=y2; x5=y3; x6=y4
X=

На примере замены x₁ на y₃ проследим ход решения задачи:

1) a₃₁x₁=y₃–b₃–a₃₂x₂=y₃–(b₃+a₃₂x₂).

2) x₁=

3)

;

Далее по аналогии:

4) ;

;

Аналогия распространяется и на уравнение w:

.

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

С этой целью используют две одинаковые по форме таблицы:

· таблицу исходных данных, в которую вносят и результаты промежуточных расчетов (табл. 2.1);

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

Таблицы 2.1 и 2.2 по форме не имеют отличий. В табл. 2.1 вносят исходные данные в левом верхнем углу, а промежуточные данные помещаются в правый нижний угол.

В табл. 2.2 в правом верхнем углу помещаются результаты замены переменных.

Решающий элемент находится на пересечении разрешающей строки (y₃) и разрешающего столбца (x₁) (в случае замены x₁ на y₃).

Подготовленная табл. 2.1 выполняет функции табл. 2.2 при необходимости продолжения операции замены для другой пары переменных.

Последовательность заполнения таблиц 2.1 и 2.2:

1. Заполнить шапку табл. 2.1, т.е. знаками переменных (X), постоянных (B) и w.

2. Заполнить шапку табл. 2.2 аналогично, поменяв местами x_i и y_j (в примере x₁ на y₃ и y₃ на x₃).

3. Заполнить табл. 2.1 исходными данными: {b_j} и {a_ij}.

4. Найти в табл. 2.2 ячейку с разрешающим элементом: обратное значение разрешающего элемента (l) записать в нижней части ячейки в табл. 2.1 и в верхней части

Таблица 2.1

Исходные и промежуточные данные расчетов

X	B	x1	x2
y1	b1–		a11		a12–
	a11b3/a31		a11/a31		a11a32/a31
y2	b2–		a21		a22–
	a21b3/a31		a21/a31		a21a32/a31
y3	b3		a31		a32
	b3/a31		l=1/a31		a32/a31
y4	b4–		a41		a42–
	a41b3/a31		a41/a31		a41a32/a31
W	g0–		g1		g2–
	g0b3/a31		g1/a31		g1a32/a31

 

 

Таблица 2.2

Терминально порождаемое отображение при замене x₁ на y₃

X	B	y3	x2
y1	Q	Ä	Q
y2	Q	Ä	Q
x1	Ä		Ä
y4	Q	Ä	Q
W	Q	Ä	Q

 

соответствующей по топологии ячейки в табл. 2.2 (a₃₁ ® l=1/a₃₁ – записать в табл. 2.1 и в табл. 2.2).

5. Уменьшить остальные элементы разрешающей строки на величину обратного элемента и записать их:

5.1) в нижнюю часть соответствующих ячеек в табл. 2.1 и в верхнюю часть ячеек в табл. 2.2 (вместо знака Ä);

5.2) выделить найденные элементы в табл. 2.1 знаком порождения.

6. Умножить элементы разрешающей строки на значение «–l» и произвести действия, аналогичные пункту 5.1.

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

7. Заполнить нижние части оставшихся ячеек в табл. 2.1 произведением значений выделенных элементов соответствующей строки и столбца и выделенных элементов разрешающей строки (b₃; a₃₂).

8. В табл. 2.2 записать разности значений, стоящих в верхней и нижней частях ячеек (в соответствии с п. 8).

 

Система «тренажер»

Для получения навыков в организации замены переменных надо воспользоваться тренажером, представленным табл. 2.3.

Тренажер изначально идентифицирован для случая и , при замене x₁ на y₃. Он представляет собой адресно-ориентированную топологию, представленную в виде системы решения элементарных подзадач.

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