П. 2. Математические основы симплексного метода

Пусть задача ЛП задана в канонической форме. Для определенности будем рассматривать задачу на нахождение максимума линейной функции. Запишем задачу ЛП в векторной форме:

Z = C X ® max,

A₁ x₁ + A₂ x₂ + … + A_n x_n = A₀, (4.1)

где С = (С₁, С₂, …, С_n), Х = (х₁, х₂, …, х_n), A_j = (a_1j, a_2j, …, a_nj), A₀ = (b₁, b₂, …, b_m).

Предположим, что согласно правилу, сформулированному в § 2, найдено некоторое первоначальное решение задачи ЛП

.

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

Условие (4.1) можно переписать следующим образом:

,

где , , …, – линейно независимые единичные векторы m-мерного векторного пространства. Они образуют базис данного пространства.

Поскольку разложение вектора по базису единственно, получим, что для вектора и любого вектора , не входящего в базис, справедливо следующее однозначное представление:

, (4.2)

(k = m + 1, …, n). (4.3)

Каждому из векторов можно поставить в соответствие значение

, (4.4)

(k = m + 1, …, n). (4.5)

Сформулируем главное утверждение данного раздела.

Теорема 4.1. (Теорема об оптимальности плана) Если для некоторого вектора выполняется условие , то план не является оптимальным и можно построить такой план Х^*, для которого выполняется условие Z(X^*) > Z(X₀).

Доказательство. Зададим некоторое число q > 0. Умножим уравнение (4.3) на q и вычтем из уравнения (4.2). Получим

. (4.6)

Поскольку значения положительны, то всегда можно подобрать такие значения q, чтобы координаты ( ) (i = 1, …, m) были неотрицательны. (Точнее все значения, кроме одного, будут положительны. Одно значение будет равно нулю, и соответствующий ему вектор выйдет из базиса.) Выражение (4.6) представляет собой разложение вектора А₀ по новому базису. Таким образом, получен новый опорный план

.

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

.

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

По предположению . Значит

Z(X^*) > Z(X₀),

Что и требовалось доказать.

Из результатов теоремы 4.1 несложно получить утверждение.

Следствие 4.1. Если для некоторого плана Х разложение всех векторов A_k (k = 1, …, n) в данном базисе удовлетворяют условию

Z_k – C_k ³ 0,

то план Х является оптимальным.

Действительно, как было показано при доказательстве теоремы 4.1 при изменении базиса в задаче ЛП, целевая функция изменяется на величину – q(Z_k – C_k). Следовательно, при неотрицательных Z_k – C_k план Х улучшить нельзя.

Теорема 4.2. Пусть для задачи ЛП

Z = C X ® min,

A₁ x₁ + A₂ x₂ + … + A_n x_n = A₀, x_i ³ 0 (i = 1, …, n),

Найден некоторый первоначальный план Х₀( ), тогда, если для некоторого вектора выполняется условие Z_k – C_k > 0, то план не является оптимальным. Можно построить такой план Х^*, для которого будет выполняться условие Z(X^*) < Z(X₀).

Следствие 4.2. Если для некоторого плана Х разложения всех векторов A_k (k = 1, …, n) в данном базисе удовлетворяют условию

Z_k – C_k £ 0,

то план Х является оптимальным.

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

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

1. находится любое опорное решение (базис m-мерного пространства) системы уравнений, соответствующих ограничениям задачи ЛП.

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

3. В случае, если план не оптимальный, согласно результатам теоремы 4.1 и теоремы 4.2, нужно ввести в базис вектор A_j, оценка которого нас не устраивает. При этом целевая функция улучшится на величину |q(Z_i – C_i)|. То есть она увеличится в задаче на максимум или уменьшится в задаче на минимум. Если имеется несколько векторов с «плохими» оценками, то для введения в базис выбирается тот, для которого соответствующее значение |q(Z_i – C_i)| наибольшее.

 

П. 3. Примеры

Рассмотрим работу симплексного метода на примерах.

П р и м е р 4.1. Найти максимальное значение целевой функции

Z = - 2х₁ + 10х₂ + 8х₃ – 12х₄

При ограничениях

Решение. Приведем систему ограничений к каноническому виду. Поскольку в системе ограничений все неравенства «£ », то дополнительные переменные прибавляются.

На данный момент существует достаточно много методических приемов использования СМ для решения задач ЛП. На наш взгляд для расчетов с использованием бумаги и ручки (и головы) удобно использовать симплексные таблицы. Они избавляют от утомительного переписывания уравнений, упорядочивают вычисления и служат своего рода органайзером. Напомним, какие действия нужно совершить и в какой последовательности.

Составим симплексную таблицу.

 

Таблица 4.1.

Базис	Сбазиса	А0	С1=-2	С2=10	С3=8	С4=-12	С5=0	С6=0	С7=0
А1	А2	А3	А4	А5	А6	А7
А5					-4	-5
А6						-1
А7					-2
Zj – Cj			–10	-8

 

Поясним устройство симплексной таблицы.

Первый столбец таблицы содержит наименование векторов, которые на данной итерации являются базисными.

Векторы в базис должны записываться в определенном порядке. Каждый вектор находится в той же строке, что единица в единичном столбике этого вектора. Например, вектор А₆ базисный. Он записывается во второй строке, поскольку единица в столбце А₆ находится во второй строке.

Во втором столбце записывается для базисного вектора A_j соответствующее значение C_j из целевой функции.

Третий столбец А₀ – это столбец свободных членов.

Последующие столбцы – это координаты векторов A_j (j = 1, 2, …, 7).

Над столбцами А₁, …, А₇ подставлены для удобства С₁, …, С₇. В строке Z_j – C_j происходит оценка плана на оптимальность. С ее помощью выбирается очередной вектор для введения в базис.

Итак, начнем решение задачи. В данном случае векторы А₅, А₆, А₇ добавленных переменных х₅, х₆, х₇ образуют базис трехмерного векторного пространства. Таким образом первоначальный опорный план Х(х₁ = 0, х₂ = 0,
х₃ = 0, х₄ = 0, х₅ = 1, х₆ = 3, х₇ = 2) получился, можно сказать, автоматически.

Проверим его на оптимальность. Для этого нужно заполнить строку
Z_j – C_j, используя формулы

Z(X₀) = С_б А₀,

Z_j – C_j = С_б А_j – C_j,

где С_б – вектор, составленный из коэффициентов целевой функции векторов, находящихся в базисе. В нашем случае С_б(С₅ = 0, С₆ = 0, С₇ = 0). С_б А₀ и
С_б А_j – скалярные произведения соответствующих векторов.

Получим:

Z₀ = 0× 1 + 0× 3 + 0× 2 = 0 (записываем значение в ячейку (Z_j – C_j; А₀)),

Z₁ – С₁ = 0× 2 + 0× 5 + 0× 4 – (–2) = 2 (записываем значение в ячейку
(Z_j – C_j; А₁))

Z₂ – С₂ = 0× 3 + 0× 6 + 0× 1 – 10 = –10 и т.д.,

.........

Z₇ – С₇ = 0× 0 + 0× 0 + 0× 1 – 0 = 0.

Обратите внимание, что в строке Z_j – C_j базисным векторам обязаны соответствовать нулевые оценки. Если это не так, ищите ошибку. Вы неправильно заполнили столбцы «Базис» и «С_базиса».

Первоначальный опорный план не является оптимальным, поскольку оценки векторов А₂ и А₃ отрицательны. Согласно теореме 4.1, чтобы улучшить план нужно ввести в базис вектора, имеющие отрицательные оценки. В данной задаче таких векторов два. Из них нужно выбрать один, который при введении в базис дает наибольшую прибыль.

Рассмотрим вектор А₂ = . Найдем отношения координат вектора А₀ к соответствующим координатам вектора А₂ и выберем из соотношений наименьшее.

.

Найдем прибыль, которая будет получена от введения вектора А₂ в базис

.

Рассмотрим вектор А₃. Проведем для него аналогичные вычисления.

(две оставшихся координаты вектора отрицательны).

.

Поскольку Z₃ > Z₂, то введение в базис вектора А₃ принесет большую выгоду. Таким образом, на следующем шаге решения в базис вводится вектор А₃, причем разрешающим элементом является координата 1 (она выделена в таблице). Заметим, что в той же строке, где находится разрешающий элемент, стоит единица базисного вектора А₆. Именно этому вектору суждено «проститься» с базисом. Составим вторую симплексную таблицу.

Таблица 4.2.

Базис	Сбазиса	А0	С1=-2	С2=10	С3=8	С4=-12	С5=0	С6=0	С7=0
А1	А2	А3	А4	А5	А6	А7
А5						-9
А3						-1
А7
Zj – Cj

 

При составлении таблицы 4.2 были проведены следующие преобразования.

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

2. К первой строке прибавляется вторая, умноженная на четыре (I+ 4II).

3. К третьей строке прибавляется вторая, умноженная на два (III + 2II).

Оценим план Х₂(х₁ = 0, х₂ = 0, х₃ = 3, х₄ = 0, х₅ = 13, х₆ = 0, х₇ = 8) на оптимальность.

Z₁ – С₁ = 8× 5 – (–2) = 42;

Z₂ – С₂ = 8× 6 – 10 = 38;

..........

Z₇ – С₇ = 0.

Поскольку среди полученных оценок нет отрицательных, то план Х₂ является оптимальным. Максимальное значение целевой функции находится в клетке (Z_j – C_j; A₀), т.е. max Z = 24.

Заметим, что при итерации мы получим прибыль 24, на которую и рассчитывали. Если при решении задачи рассчитанное при выборе разрешающего элемента значение Δ Z не совпадает с полученным в таблице, вы ошиблись в расчетах.

П р и м е р 4.2. Минимизировать функцию

Z = 66х₁ + 37х₂ + 70х₃

при ограничениях

Решение. Приведем задачу к каноническому виду

Z = 66х₁ + 37х₂ + 70х₃ + 0х₄ +0х₅,

Составим симплексную таблицу

Таблица 4.3.

Базис	Сбазиса	А0	С1=66	С2=37	С3=70	С4=0	С5=0
А1	А2	А3	А4	А5
- -	- -					-1	-1
А1 -	-	1/2 9/2		1/3	1/6 27/2	-1/12 1/4	-1	I: 12 II – 3I
А1 А2		1/5 9/10			-11/15 27/10	-1/10 1/20	1/5 -1/5	I – 1/3 II II: 5
Zj – Cj	46, 5			-18, 5	-5, 75	-3

 

Дадим необходимые пояснения.

Во-первых, в отличие от примера 4.1 в данном случае первоначального опорного плане не было. Поэтому надо получить первоначальный опорный план. Векторы выбирались наугад, поскольку не было возможности оценить выгоду от введения того или иного вектора в базис. Случайно для базиса А₁, А₂ не оказалось положительных оценок, т.е. план Х(х₁ = 0, 2, х₂ = 0, 9, х₃ = 0, х₄ = 0, х₅ = 0) является оптимальным. Соответствующее значение целевой функции

Z_min = 66 × 0, 2 + 37 × 0, 9 = 46, 5.

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться: