3.2. Приклад застосування симплекс-методу

Крок 1. Ще раз повторимо формулювання задачі з нашого приклада.

F = 2 x₁ + 4 x₂ → max;

4 x₁ +6 x₂  120,

2 x₁ +6 x₂  72,

x₂  10;

x₁ ≥ 0, x₂ ≥ 0.

Крок 2. Виконаємо другий крок для нашого приклада.

4x₁ +6x₂ + x₃ = 120,

2 x₁ +6 x₂ + x₄ = 72,

x₂ + x₅ = 10.

Малюнок 2.2 - Загальна схема симплекс-алгоритму

Крок 3.

Таблиця 2.5 - Вихідна симплекс-таблиця для задачі про хокейні ключки й шахові набори

Базис	Змінні					bi
	x1	x2	x3	x4	x5
x3	4	6	1	0	0	120
x4	2	6	0	1	0	72
x5	0	1	0	0	1	10
cj	-2	-4	0	0	0	0

Таким чином, у даному базисному рішенні неосновні змінні x₁ і x₂ дорівнюють нулю. Базисні змінні відмінні від нуля: x₃ = 120, x₄ = 72, x₅ = 10. Дане базисне рішення є припустимим. Природно, що значення цільової функції в цьому випадку дорівнює нулю, тому що у формуванні цільової функції беруть участь змінні, які для даного базисного рішення є неосновними.

Крок 4. У нашій задачі останній рядок містить два позитивних елементи, отже, необхідно перейти до кроку 5.

Крок 5. У нашій задачі в якості вирішального виберемо другий стовпець (що відповідає змінній x₂), оскільки в останньому рядку для цього стовпця міститься 4.

Крок 6. У нашім прикладі всі елементи вирішального стовпця позитивні (6, 6 і 1), отже, необхідно перейти до кроку 7.

Крок 7. Проілюструємо виконання кроку 7, звернувшись до нашого приклада.

Для першого рядка: D₁ = 120/6 = 20.

Для другого рядка: D₂ = 72/6 = 12.

Для третього рядка: D₃ = 10/1 = 10.

Найменший результат ділення - у третьому рядку, значить саме цей рядок ми обираємо в якості вирішального, тобто виключати з базисного рішення будемо змінну x₅.

У нашім випадку вирішальним елементом є одиниця, що стоїть на перетині третього рядка й другого стовпця.

Вихідна симплекс-таблиця нашого приклада з виділеними кольором вирішальним рядком і вирішальним стовпцем представлена нижче (таблиця 2.6).

Таблиця 2.6 - Вихідна симплекс-таблиця з виділеними вирішальним рядком і стовпцем, а також з ілюстрацією до застосування правила прямокутника

Базис	Змінні					bi
	x1	x2	x3	x4	x5
x3	4 	 6	1	0	0	120
x4	2 	 6	0	1	0	72
x5	0 	 1	0	0	1	10
cj	-2	-4	0	0	0	0

Крок 8. Застосування правила прямокутника проілюструємо, використовуючи таблицю 2.6. Перерахуємо елемент a₁₁ (у вихідній симплекс-таблиці його значення дорівнює 4). У таблиці 2.6 можна побачити прямокутник (прокреслений пунктиром), що з'єднує чотири елементи, які беруть участь у перерахуванні:

a₁₁=a₁₁- a₁₂  a₃₁ / a₃₁, тобто a₁₁=4 – 6  0 / 1 = 4.

Аналогічним способом перераховуються інші елементи.

По закінченні перерахування здійснюється повернення до кроку 4.

Повністю результат перерахування для нашого приклада можна побачити в таблиці 2.7

Таблиця 2.7 - Симплекс-Таблиця для задачі про хокейні ключки й шахові набори (друге базисне рішення)

Базис	Змінні					bi
	x1	x2	x3	x4	x5
x3	4	0	1	0	-6	60
x4	2	0	0	1	-6	12
x2	0	1	0	0	1	10
cj	-2	0	0	0	4	40

Таким чином, у новому базисному рішенні базисними змінними є: x₂ = 10, x₃ = 60, x₄ = 12 (відповідні значення можна побачити в останньому стовпці таблиці). Неосновні змінні x₁ і x₅ дорівнюють нулю. Значення цільової функції в цьому випадку дорівнює 40 (значення можна побачити в правому нижньому осередку таблиці).

Доведемо рішення нашого приклада до кінця.

Повернемося до кроку 4 симплекс-алгоритму. Розглянемо останній рядок таблиці 2.7. У ній є позитивні елементи, значить отримане рішення не є оптимальним.

Крок 5. Виберемо вирішальний стовпець. Їм виявиться стовпець x₁, оскільки тут міститься єдиний позитивний елемент нижнього рядка. Стало бути, змінну x₁ будемо переводити в основні.

Далі. Крок 6. Перевірка показує, що в розв'язному стовпці є позитивні елементи, отже, можна продовжувати рішення.

Крок 7. Визначимо вирішальний рядок. При цьому будемо розглядати лише перший й другий рядки, оскільки для третього рядка в вирішальному стовпці перебуває нуль. Знайдемо частку від ділення елемента b_i на елемент, що перебуває в вирішальному стовпці:

Для першого рядка: D₁ = 60/4 = 15.

Для другого рядка: D₂ = 12/2 = 6.

Найменший результат ділення - у другому рядку, значить саме цей рядок ми вибираємо в якості вирішального, тобто переводити в неосновні (виключати з базису) будемо змінну x4.

Нижче наведена симплекс-таблиця з виділеними вирішальним рядком і стовпцем (таблиця 2.8).

Таблиця 2.8 - Симплекс-Таблиця (друге базисне рішення) з виділеними вирішальним рядком і стовпцем

Базис	Змінні					bi
	x1	x2	x3	x4	x5
x3	4	0	1	0	-6	60
x4	2	0	0	1	-6	12
x2	0	1	0	0	1	10
cj	-2	0	0	0	4	40

Далі перейдемо до кроку 8 і здійснимо перерахування елементів симплексної таблиці відповідно до правил, що приводяться вище. Результат перерахування представлений у таблиці 2.9.

Таким чином, у черговому (третьому) базисному рішенні основними змінними є: x₁ = 6, x₂ = 10, x₃ = 36. Неосновні змінні x₄ і x₅ дорівнюють нулю. Значення цільової функції для цього рішення дорівнює 52.

Повернемося до кроку 4 симплекс-алгоритму. Розглянемо останній рядок таблиці 2.9. У ній усе ще є позитивні елементи, значить отримане рішення не є оптимальним, і необхідно продовжити виконання симплекс-алгоритму.

Таблиця 2.9 - Симплекс-таблиця для задачі про хокейні ключки й шахові набори (третє базисне рішення)

Базис	Змінні					bi
	x1	x2	x3	x4	x5
x3	0	0	1	-2	6	36
x1	1	0	0	1/2	-3	6
x2	0	1	0	0	1	10
cj	0	0	0	1	-2	52

Крок 5. Виберемо вирішальний стовпець. Їм виявиться стовпець x₅, оскільки тут міститься єдиний позитивний елемент нижнього рядка. Змінну x₅ будемо переводити в основні.

Крок 6. Перевірка показує, що в вирішальному стовпці є позитивні елементи, отже, можна продовжувати рішення.

Крок 7. Визначимо вирішальний рядок. При цьому будемо розглядати лише перший й третій рядки, оскільки для другого рядка в вирішальному стовпці знаходиться негативне число. Знайдемо частку від ділення елемента b_i на елемент, що перебуває в вирішальному стовпці:

Для першого рядка: D₁ = 36/6 = 6.

Для третього рядка: D₂ = 10/1 = 10.

Найменший результат ділення - у першому рядку, значить саме цей рядок ми вибираємо в якості вирішального, тобто переводити в неосновні (виключати з базису) будемо змінну x₃.

Нижче наведена симплекс-таблиця з виділеними вирішальним рядком і стовпцем (таблиця 2.10).

Таблиця 2.10 - Симплекс-таблиця (третє базисне рішення) з виділеними вирішальним рядком і стовпцем

Базис	Змінні					bi
	x1	x2	x3	x4	x5
x3	0	0	1	-2	6	36
x1	1	0	0	1/2	-3	6
x2	0	1	0	0	1	10
cj	0	0	0	1	-2	52

Далі перейдемо до кроку 8 і здійснимо перерахування елементів симплексної таблиці відповідно до правил, що приводяться вище. Результат перерахування представлений у таблиці 2.11.

Таблиця 2.11 - Симплекс-таблиця для задачі про хокейні ключки й шахові набори (четверте базисне рішення)

Базис	Змінні					bi
	x1	x2	x3	x4	x5
x5	0	0	1/6	-1/3	1	6
x1	1	0	1/2	-1/2	0	24
x2	0	1	-1/6	1/3	0	4
cj	0	0	1/3	1/3	0	64

Таким чином, у черговому (четвертому) базисному рішенні основними змінними є: x₁ = 24, x₂ = 4, x₅ = 6. Неосновні змінні x₃ і x₄ дорівнюють нулю. Значення цільової функції для цього рішення дорівнює 64.

Повернемося до кроку 4. Розглянемо останній рядок таблиці 2.11. Позитивних елементів у ній не залишилося, отже отримане рішення є оптимальним. Рішення задачі знайдене. Воно, що природно, збігається з рішенням, отриманим для цієї ж задачі за допомогою графічного методу:

x₁^* = 24, x₂^* = 4, F₀^*=64.