2.2.3 Решение задачи симплексным методом

ИТЕРАЦИЯ 1

ШАГ 1. Выписываем исходное допустимое базисное решение

Х₁ Х₂ Х₃ Х₄ Х₅

Х₁ =

0 0 60 34 8

и соответствующее ему значение целевой функции Z.

Z = 2 * 0 + 3 * 0 + 0 * 60 + 0 * 34 + 0 * 8 = 0.

ШАГ 2. Проверяем оптимальность полученного решения.

Пусть Δ Х₁ = 1

Тогда Δ Х₃ = -3

Δ Х₄ = -3

Δ Х₅ = 0

Δ Z = 2 * 1 + 3 * 0 + 0 * (-3) + 0 * (-3) + 0 * 0 = 2 > 0.

Вывод: Решение Х₁ неоптимальное. Переменную Х₁ целесообразно ввести в базис поскольку от этого значение целевой функции Z увеличится.

ШАГ 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

Х₃ = 60 - 3Х₁ 60 - 3Х₁ > 0 Х₁ > 20

34

Х₄ = 34 - 3Х₁ = > 34 - 3Х₁ > 0 = > Х₁ > --- (*)

3

Х₅ = 8 - 0 -- --

Замена прежней базисной переменной произойдет во втором уравнении.

Вывод: В новом базисе будут находиться переменные Х1, Х3, Х5, а переменная Х4 станет небазисной.

ШАГ 4. Пересчет системы линейных уравнений с учетом нового состава базисных переменных.

Для этого:

1. Разделим почленно второе уравнение системы (2) на 3. Это будет второе уравнение новой системы (3).

2. Исключим переменную Х₁ из первого уравнения. Для этого из первого уравнения системы (2) вычтем второе уравнение системы (3), умноженное на 3:

3Х₁ + 5Х₂ + Х₃ = 60

3Х₁ + 4Х₂ + Х₄ = 34

Х₂ + Х₃ - Х₄ = 26

Это будет первое уравнение новой системы (3).

2. Перепишем в новую систему уравнений (3) третье уравнение из системы (2) в том же виде

После таких преобразований новая система уравнений будет иметь вид:

Х₂ + Х₃ - Х₄ = 26

4 1 34

Х₁ + --Х₂ + -- Х₄ = -- (3)

3 3 3

Х₂ + Х₅ = 8

ИТЕРАЦИЯ 2

ШАГ 1. Выписываем очередное допустимое базисное решение:

Х₁ Х₂ Х₃ Х₄ Х₅

Х₂ = 34

--- 0 26 0 8

3

и соответствующее ему значение целевой функции:

34 68

Z = 2 * --- + 3 * 0 + 0 * 26 + 0 * 0 + 0 * 8 = ---

3 3

ШАГ 2. Проверяем оптимальность полученного решения.

Пусть Δ Х₂ = 1

Тогда Δ Х₃ = - 1

4

Δ Х₁ = - --

3

Δ Х₅ = - 1

4 8

Δ Z = 2 * (- --- ) + 3 * 1 + 0 * (- 1) + 0 * 0 + 0 * (- 1) = - --- + 3 > 0

3 3

Вывод: Решение Х₂ не оптимальное. Переменную Х₂ целесообразно ввести в базис, поскольку от этого значение целевой функции увеличится.

ШАГ 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

Х₃ = 26 - Х₂ 26 - Х₂ > 0 Х₂ < 26

34 4 34 4 34

Х₁ = --- - --Х₂ => --- - --- Х₂ > 0 => Х₂ < ---

3 3 3 3 4

Х₅ = 8 - Х₂ 8 - Х₂ > 0 Х₂ < 8 (* )

Вывод: В третьем уравнении базисной станет переменная Х₂, а переменная Х₅ выйдет из базиса.

ШАГ 4. Пересчет системы линейных уравнений с учетом нового состава базисных переменных.

Так как в системе (3) в третье уравнение переменная Х2 входит с коэффициентом +1, перепишем его в том же виде в новую систему (4) третьим уравнением.

Преобразуем систему уравнений (3) так, чтобы переменная Х2 отсутствовала в первых двух уравнениях.

Для этого:

1. Исключим переменную Х₂ из первого уравнения (из первого уравнения системы (3) вычтем третье уравнение новой системы (4)):

Х₂ + Х₃ - Х₄ = 26

Х₂ + Х₅ = 8

Х₃ - Х₄ - Х₅ = 18

Получим первое уравнение новой системы (4).

2. Исключим переменную Х₂ из второго уравнения (из второго уравнения системы (3) вычтем третье уравнение системы (4), умноженное на 4/3):

4 1 34

Х₁ + --Х₂ + -- Х₄ = ---

3 3 3

4 4 32

--Х₂ + -- Х₅ = ---

3 3 3

1 4 2

Х₁ + --Х₄ - --Х₅ = --

3 3 3

Получим второе уравнение новой системы (4).

После преобразований новая система уравнений будет иметь вид:

Х₃ - Х₄ - Х₅ = 18

1 4 2

Х₁ + --Х₄ - --Х₅ = -- (4)

3 3 3

Х₂ + Х₅ = 8

ИТЕРАЦИЯ 3.

ШАГ 1. Выписываем очередное допустимое базисное решение:

Х₁ Х₂ Х₃ Х₄ Х₅

Х₃ = 2

-- 8 18 0 0

3

и соответствующее ему значение целевой функции:

2 76 1

Z = 2 * --- + 3 * 8 + 0 * 18 + 0 * 0 + 0 * 0 = --- = 25 ---

3 3 3

ШАГ 2. Проверяем оптимальность полученного решения.

Пусть Δ Х₄ = 1

Тогда Δ Х₃ = 1

1

Δ Х₁ = - --

3

Δ Х₂ = 0

1 2

Δ Z = 2 * (- ---) + 3 * 0 + 0 * 1 + 0 * 1 + 0 * 0 = - --- < 0.

3 3

Вывод: Так как Δ Z < 0, переменную Х₄ нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.

Шаг 2 продолжается.

Пусть Δ Х₅ = 1

Тогда Δ Х₃ = 1

4

Δ Х₁ = --

3

Δ Х₂ = - 1

4 8

Δ Z = 2 * --- + 3 * (- 1) + 0 * 1 + 0 * 0 + 0 * 1 = --- - 3 < 0.

3 3

Вывод: Так как Δ Z < 0, переменную Х₅ нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.

Вывод по шагу 2: Поскольку на данной итерации ни одну из небазисных переменных нецелесообразно вводить в базис, решение Х₃ является оптимальным.

Как можно заметить, среди компонент оптимального плана есть нецелые:

2

Х₁ =

3

Согласно алгоритму решения задач целочисленного линейного программирования, построим правильное отсечение по второму уравнению, где получилось нецелочисленное значение:

1 4 2

--- Х₄ - --- Х₅ > ---

3 3 3

т.е.

1 2 2

-- Х₄ + --Х₅ > -- ( 5)

3 3 3

П римечание 1. Символ … означает дробную часть числа. Дробной частью а числа а называется разность между этим числом и его целой частью [а ], т.е. наибольшим целым числом, не превосходящим а.

1

Например, если а = 2--- , то

3

1 1 1 1 1

2 -- = 2-- - [ 2-- ] = 2-- - 2 = --

3 3 3 3 3

21/3

0 1 2 3 х

1

если а = - 2 -- , то

3

1 1 1 1 2

- 2 -- = - 2-- - [ - 2-- ] = - 2-- + 3 = --

3 3 3 3 3

- 21/3

-3 -2 -1 0 х

Сформируем новую систему (6), добавив в систему (4) полученное правильное отсечение (5):

Х₃ - Х₄ - Х₅ = 18

1 4 2

Х₁ + --Х₄ - --Х₅ = --

3 3 3

Х₂ + Х₅ = 8 (6)

1 2 2

--Х₄ + --Х₅ > --

3 3 3

Продолжим решение нашей задачи. Для этого сначала нужно записать задачу (6) в каноническом виде, добавив в четвертое ограничение переменную Х6 с коэффициентом (-1), а затем построить вспомогательную задачу, добавив в четвертое ограничение искусственную переменную Х₇.

Вспомогательная задача будет иметь следующий вид:

Х₃ - Х₄ - Х₅ = 18

1 4 2

Х₁ + --Х₄ - --Х₅ = --

3 3 3

Х₂ + Х₅ = 8 (7)

1 2 2

--Х₄ + --Х₅ - Х6 + Х7 = --

3 3 3

Хj > 0, j = 1, 7; Х₁, Х₂ – целые числа

Z = 2 *Х₁ + 3*Х₂ + 0*Х₃ + 0*Х₄ + 0*Х₅ - 0*Х₆ - М*Х₇ = > max

ИТЕРАЦИЯ 4

ШАГ 1. Выписываем очередное допустимое базисное решение:

Х1 Х2 Х3 Х4 Х5 Х6 Х7

Х₄ = 2 2

-- 8 18 0 0 0 --

3 3

и соответствующее ему значение целевой функции.

2 2 76 2

Z = 2 * -- + 3 * 8 + 0 * 18 + 0 * 0 + 0 * 0 - 0 * 0 - --М = --- - --М > 0

3 3 3 3

ШАГ 2. Проверяем оптимальность полученного решения.

Пусть Δ Х₄ = 1

Тогда Δ Х₃ = 1

1

Δ Х₁ = - --

3

Δ Х₂ = 0

1

Δ Х₇ = - --

3

1 1 2 1

Δ Z = 2 * (- -- ) + 3 * 0 + 0 * 1 + 0 * 1 + 0 * 0 - 0 * 0 - М (- -- ) = - -- + --М > 0

3 3 3 3

Вывод: Решение Х₄ неоптимальное. Переменную Х₄ целесообразно ввести в базис, поскольку при этом значение целевой функции увеличится.

ШАГ 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

Х ₃ = 18 + Х₅ - -

2 4

Х₁ = -- + -- Х₅ - -

3 3

Х₂ = 8 - Х₅ => 8 - Х₅ > 0 => Х₅ < 8

2 2 2 2

Х₇ = --- - --- Х₅ -- - --Х₅ > 0 Х₅ < 1 (*)

3 3 3 3

Вывод: Замена базисной переменной должна произойти в четвертом уравнении. Переменная Х₅ станет базисной, а искусственная переменная Х₇ выйдет из базиса.

ШАГ 4. Пересчет системы линейных уравнений с учетом нового состава базисных переменных.

Преобразуем систему уравнений (7) так, чтобы в четвертое уравнение новой системы (8) переменная Х₅ вошла с коэффициентом +1, и отсутствовала бы в трех других.

Для этого:

1. Получим четвертое уравнение новой системы (8). Для чего четвертое уравнение системы (7) почленно умножим на 3/2 и коэффициент при Х₅ станет равным +1.

2. Исключим переменную Х₅ из трех первых уравнений системы (7). Получим три первые уравнения новой системы (8).

После преобразований новая система уравнений будет иметь вид:

1 3 3

Х₃ - -- Х₄ - -- Х₆ + -- Х₇ = 19

2 2 2

Х₁ + Х₄ - 2Х₆ + 2Х₇ = 2

1 3 3

Х₂ - --Х₄ + --Х₆ - -- Х₇ = 8 (7)

2 2 2

1 3 3

--Х₄ + Х₅ - --Х₆ + --Х₇ = 1

2 2 2

ИТЕРАЦИЯ 5

ШАГ 1. Выписываем очередное допустимое базисное решение:

Х1 Х2 Х3 Х4 Х5 Х6 Х7

Х₅ =

2 7 19 0 1 0 0

и соответствующее ему значение целевой функции:

Z = 2 * 2 + 3 * 7 + 0 * 19 + 0 * 0 + 0 * 1 - 0 * 0 - М * 0 = 25

ШАГ 2. Проверяем оптимальность полученного решения.

Пусть Δ Х₄ = 1

1

Тогда Δ Х₃ = --

2

Δ Х₁ = - 1

1

Δ Х₂ = --

2

1

Δ Х₅ = - --

2

1 1 1 1

Δ Z = 2 * (-1) + 3 * -- + 0 * -- + 0 * 1 + 0 * (- -- ) - 0 * 0 - М * 0 = - -- < 0

2 2 2 2

Вывод: Так как Δ Z < 0 , переменную Х₄ нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.

Шаг 2 продолжаем.

Пусть Δ Х₆ = 1

3

Тогда Δ Х₃ = --

2

Δ Х₁ = 2

3

Δ Х₂ = - --

2

3

Δ Х₅ = --

2

3 3 3 1

Δ Z = 2 * 2 + 3 * (- -- ) + 0 * -- + 0 * 0 + 0 * -- - 0 * 1 - М * 0 = - -- < 0

2 2 2 2

Вывод: Так как Δ Z < 0 , переменную Х₆ нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.

Вывод по шагу 2: Поскольку на данной итерации ни одну из небазисных переменных нецелесообразно вводить в базис, решение Х₅ является оптимальным.