Методика решения ЗЛП методом симплекс- таблиц

Практическая реализация ручного счета при использовании симплекс – метода в настоящее время используется в виде, так называемых, симплекс -таблиц, позволяющих в значительной мере формализовать процесс симплекс преобразований на каждом шаге. Такой метод решения ЗЛП получил название метод симплекс-таблиц. Вычислительной основой для реализации этого метода является метод полного исключения (метод Жордана – Гаусса).

Для определенности будем полагать, что задача решается но максимум целевой функции. Задача решается поэтапно.

Этап 1. После введения добавочных пере6менных систему уравнений ограничений и линейную форму (целевую функцию) запишем в виде расширенной постановки задачи

a₁₁x₁ + a₁₂x₂ + …+ a_1nx_n + x_n+1 = b₁,

a₂₁x₁ + a₂₂x₂ + …+ a_2nx_n + x_n+2 = b₂, (10.1)

……………………………………..

a_m1x₁ + a_m2x₂ + …+ a_mnx_n + x_n+m = b_m.

F – c₁x₁ – c₂x₂ - … - c_nx_n = 0. (10.2)

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

Этап 2. Исходную расширенную систему заносим в первую симплекс таблицу (таблица 10.1)

Таблица 10.1 – Исходная симплекс – таблица

i

Базис

сб

P0

c1

c2

...

cr

...

cm

cm+1

...

ck

...

cn

P1

p2

...

Pr

...

Pm

Pm+1

...

Pk

...

Pn

P1

c1

b1

...

...

a1m+1

...

a1k

...

a1n

P2

c2

b2

...

...

a2m+1

...

a2k

...

a2n

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

r

Pr

cr

br

...

...

arm+1

...

ark

...

arn

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

m

Pm

cm

bm

...

...

amm+1

...

amk

...

amn

m+1

F0

...

...

m+1

...

k

...

n

Таблица имеет m + 1 строку, где m – число базисных (основных) переменных. В последнюю (m + 1) записывается линейная форма. Эта строка таблицы называется оценочной.

Таблица имеет n + 4 столбца, где n – общее число переменных в расширенной задаче (заполняются, начиная с мятого столбца).

Столбец 1 – номер строки (1, 2, …, m, m+1).

Столбец 2 – Обозначение базисного вектора Р₁, Р₂, …, P_r, …, P_m.

В столбце 3 (С_б ) таблицы записывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса.

В столбце 4 (Р_о) записывают положительные компоненты исход­ного опорного плана (свободные члены соответствующих уравнений). В нем же в результате вычислений получают положительные компоненты оптимального плана. Столбцы 5 - n +4 – столбцы век­торов P_j. Вних заполняюткоэффициенты a_ij расширенной системы уравнений ограничений (разложения этих векторов по векторам данного базиса.

В таблице 3.1 первые m строк определяются исходными дан­ными задачи, а показатели (m + 1)-й строки вычисляют. В этой строке в столбце вектора Р_о записывают значение целевой функ­ции, которое она принимает при данном опорном плане, а в столб­це вектора Р_j — значение _j = z_j — с_j.

Значение z_j - вычисляется как скалярное произведение вектора P_j (j=l, n) на вектор C_б =(c₁; c₂;...; с_m):

z_j = (j= 1, n) (10.3)

Значение F₀ равно скалярному произведению вектора P_о на вектор С_б:

F_{0 =} .(10.4)

Далее таблица преобразуется по строго определенным формальным правилам.

Этап 3. После заполнения таблицы 10.1 исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки таблицы. В результате может иметь место один из следующих трех случаев:

1) _j ³ 0 для j = m+1, m+2,..., n(при j= ; z_j = c_j). Поэтому в данном случае числа _j ³ 0 для всех j от 1 до n;

2) _j < 0 для некоторого j, и все соответствующие этому индексу величины a_ij £ 0(i=l, m);

3) _j < О для некоторых индексов j, и для каждого такого j по крайней мере одно из чисел a_ij положительно.

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

Во втором случае целевая функция не ограничена сверху на множестве планов (задача не имеет решения).

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

Этап 4. Переход от одного опорного плана к другому осу­ществляется исключением из исходного базиса одного из векторов и введением в него нового вектора.

В качестве век­тора, вводимого в базис, можно взять любой из векторов Р_j, имеющий индекс j, для которого _j < 0. Если таких столбцов несколько, то целесообразно взять тот столбец, у которого _j по абсолютной величине наибольшее. Пусть, например, _k < 0 и решено ввести в базис вектор P_k. Если же таких чисел несколько, то в базис вводят вектор, имеющий такой же индекс, как и максимальное из чисел С_j, опре­деляемых данными числами _j ( _j < 0).

В данном случае, столбец, в котором записаны элементы вектора P_k называют направляющим.

Для определения вектора, выводимого (исключаемого) из ба­зиса, определяют минимум отношения min (b_i/a_ik) для всех а_ik > 0 (направляющего столбца). Пусть этот минимумдостигается при i = r. Тогда эту (i) строку называют направляющей, ииз базиса исключают вектор Р_г, а число a_rk, находящееся на пересечении направляющего столбца и направляющей строки) называют разрешающим элементом.

При получении значения этого отношения могут возникнуть следующие ситуации:

- b_i и a_ir имеют разные знаки. Отношение принимается равным ∞ $;

- b_i = 0 и a_ir < 0. Отношение принимается равным ∞;

- a_ir = 0. Отношение принимается равным ∞;

- b_i = 0 и a_ir > 0. Отношение принимается равным 0;

- если b_i^C и a_ik^C имеют одинаковые знаки. Отношение принимается равным .

Этап 5. После выделения направляющей строки и направляющего столбца вычисляют новый опорный план и коэффициенты разложе­ния векторов P_j через векторы нового базиса, соответствующего новому опорному плану. Составляется новая (в данном случае вторая) симплекс – таблица.

Получение новых элементов таблицы осуществляется на основе метода исключений (метода Жордана—Гаусса). При этом элементы новой таблицы вычисля­ются по формулам:

а) элементы столбца Р₀:

(10.5)

для строки, соответствующей направляющей в старой (в данном случае первой) таблице;

(10.6)

где r –индекс (нижний) направляющей строки;

k - индекс (нижний направляющего столбца;

Н – индекс (верхний) элемента новой таблицы;

С - индекс (верхний) элемента старой таблицы.

Из этих обозначений следует, что a_rk – разрешающий элемент;

б) коэффициенты разложения векторов P_j через векторы нового базиса, соответствующего новому опорному плану— по форму­лам:

(10.7)

для строки, соответствующей направляющей в старой (в данном случае первой) таблице;

(10.8)

После вычисления b_i^Ни a_ij^Н согласно формулам (10.5)- (10.8) их значения заносят в новую таблицу.

Элементы (m+1)-й строки новой таблицы могут быть вычислены по формулам

- (10.10)

скалярное произведение векторов с_б и Р₀ новой таблицы;

_- (10.11)

скалярное произведение векторов с_б и Р_i новой таблицы минус с_j.

Если же таких чисел несколько, то в базис будем вводить вектор, имеющий такой же индекс, как и максимальное из чисел С_j, опре­деляемых данными числами _j ( _j < 0).

Итак, переход от одного опорного плана к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы но­вой симплекс-таблицы можно вычислить как с помощью рекур­рентных формул (10.5) — (10.11), так и по правилам, непосредственно вытекающим из них. Эти правила состоят в следующем.

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

Элементы векторов P₀ и P_j в строке новой симплекс-таблицы, в которой записан вектор, вводимый в базис, получают из эле­ментов этой же строки исходной таблицы делением их на вели­чину разрешающего элемента. В столбце с_б в строке вводимого вектора проставляют величину с_k, где k — индекс вводимого век­тора.

Остальные элементы столбцов вектора Р_о и P_j новой сим­плекс-таблицы вычисляют по правилу треугольника. Для вычисления какого-нибудь из этих элементов получают три числа:

1) число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;

2) число, стоящее в исходной симплекс-таблице на пересече­нии строки, в которой находится искомый элемент новой сим­плекс-таблицы, и столбца, соответствующего вектору, вводимому в базис;

3) число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и строки вновь вводимого в базис вектора (эта строка получа­ется из строки исходной симплекс-таблицы делением ее элемен­тов на разрешающий элемент).

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

Отметим, что в некоторых источниках это правило трактуется, как правило прямоугольника и графически изображается так как показано на рисунке 10.1.

Рисунок 10.1 – Графическое изображение правила прямоугольника

После заполнения новой симплекс-таблицы вновь просматривают элементы (m+1)-й строки. Если все ∆ _jj ³ 0, то новый опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то, используя описанную последо­вательность действий, вычисляют новый опорный план. Этот процесс продолжают до тех пор, пока либо не получают оптимальный план задачи, либо не устанавливают ее неразре­шимость.

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

Итак, вычисление оптимального плана симплексным методом включает следующие этапы:

1) вычисляют опорный план;

2) составляют симплекс-таблицу;

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

4) вычисляют направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отри­цательным числом _j, а направляющая строка — минимальным из отношений компонент столбца вектора P₀ к положительным компонентам направляющего столбца;

5) по формулам (10.5) — (10.11) определяют положительные ком­поненты нового опорного плана, коэффициенты разложения век­торов P_j по векторам нового базиса и числа F₀^Н, _j^Н. Все эти числа записываются в новую симплекс-таблицу;

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