Симплекс-метод розв’язання задач лінійного програмування

Сутність методу полягає у послідовному переборі багатокутника допустимих рішень, починаючи з деякої базисної точки, до того ж кожний наступний варіант перебору повинен бути не гірше від попереднього.

Нехай необхідно мінімізувати лінійну цільову функцію F при наявності m незалежних лінійних обмежень з n невідомими x_i.

Якщо система рівнянь незалежна, то число вільних змінних дорівнює (n-m=k), а число базисних змінних дорівнює x_і. (i=m)

Вільні змінні позначаємо x₁,x₂,…,x_k, а базисні змінні x_k+1,x_k+2,…x_n.

Припустимо, що вдалося одну частину змінних – базисні виразити через іншу частину змінних – вільні. Тоді задачу лінійного програмування в загальному вигляді можна записати наступним чином:

– функція вільних змінних (9)

при

– базисні змінні (10)

Далі припустимо, що x₁=x₂=…=x_k =0. Тоді базисні змінні приймуть значення:

(11)

Отримуємо одне з базисних рішень. Воно може бути допустимим чи не допустимим. Якщо невід’ємні, то отримане рішення допустиме.

Це перше рішення може бути оптимальним чи неоптимальним.

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

Позначимо:

Отримаємо: (12)

(13)

Якщо коефіцієнти усі від’ємні, то збільшуючи змінні, ми не можемо далі мінімізувати ЦФ F, і отриманий розв’язок буде оптимальним.

Якщо ж серед коефіцієнтів є додатні, то збільшуючи ті зі змінних, у яких коефіцієнти додатні, можна зменшувати значення ЦФ F.

Виберемо одну зі змінних , для якої коефіцієнти в ЦФ додатні. Якщо збільшувати, то ЦФ буде зменшуватися. Причому збільшувати можна до тих пір, поки з базисних змінних, зменшуючись не обернеться в нуль.

Перепишемо систему обмежень у спрощеному вигляді:

Збільшення не викликає зменшення базисних змінних, у яких і за їх зміною можна не стежити.

Розглянемо базисні змінні, у яких .

Базисна змінна обертається в нуль при

Оберемо серед усіх відношень найменше і нехай воно відповідає L-й базисній змінній:

Тоді при зростанні першого обертається в нуль змінна при значенні рівному . Інші базисні змінні будуть при цьому невід’ємні. Коефіцієнт називається розв’язуючим елементом.

Таким чином, щоб визначити максимально допустиме значення вільної змінної , ми повинні знайти розв’язуючий елемент .

Далі вільну змінну і базисну змінну міняємо місцями. Вийде новий вибір базисних змінних

Цільову функцію F і базисні змінні виразимо через нові вільні змінні. Якщо тепер коефіцієнти у ЦФ F виявляться всі від’ємні, то оптимальний розв’язок знайдений. Якщо деякі будуть мати додатні значення, то систему треба розв’язувати відносно інших базисних змінних до тих пір, поки всі коефіцієнти при змінних у ЦФ F не виявляться від’ємними.

Приклад №4. Розглянемо розв’язок задачі із застосуванням симплекс – методу використовуючи умови попереднього 3-го прикладу.

Цільова функція:

Обмеження:

Перетворимо систему обмежень, яка задані у вигляді нерівностей, у систему рівностей, увівши додаткові базисні змінні. Якщо знак обмеження «>», то ставиться «-», якщо «<», то ставиться «+»:

У якості вільних змінних приймемо х₁ та х₂ і виразимо базисні змінні х₃, х₄, х₅ через вільні і складемо нову систему рівнянь:

(14)

Цільова функція прийме вигляд:

(15)

Представимо вирази (14) і (15) у вигляді таблиці. Значення вільних членів рівнянь і коефіцієнтів при змінних записуємо у верхньому лівому куті відповідної ячійки. Таблиця №1.

розв’язуючий стовпець (×-λ)

	Вільний член рівняння	Х1	Х2
F		- 4 -4	- 12
X3	-180	0,6 0,6	0,6
X4	-300	- 1 РЕ -1	-1
X5	- 100	0	- 1

Подальший розрахунок і аналіз доцільно звести до послідовного виконання трьох алгоритмів.

9.3.1. Алгоритм знаходження розв’язуючого елементу:

1. Знаходимо перше від’ємне значення в стовпці для вільних членів, окрім рядка F; у нашому випадку , і в цьому рядку обираємо любий від’ємний елемент. Цим визначається розв’язуючий стовпець.

2. В якості кандидатів на роль розв’язуючого елемента розглядаються всі елементи стовпця, які одинакові за знаком з вільним членом свого рядка.

Для цих елементів знаходимо відношення вільних членів рівняння до відповідних коефіцієнтів (елементів) розв’язуючого стовпця, які одинакові за знаком з вільним членом свого рядка, окрім рядка F:

3. Обираємо мінімальне значення отриманих відношень, яке визначає розв’язуючий елемент (РЕ).

4. Позначаємо РЕ подвійним кутком.

У даному випадку розв’язуючим елементом є , тому систему перерозв’язуємо відносно та .

9.3.2. Алгоритм перетворення таблиці шляхом заміни вільних і базисних змінних:

1. Розв’язуючий елемент () виділяється в таблиці (позначен подвійним кутком).

2. Визначається відношення і записується в нижньому правому куті ячійки РЕ (-1).

3. Всі елементи розв’язуючого рядка, окрім РЕ, помножуються на λ і результати записуються у нижньому правому куті відповідних ячійок таблиці.

4. Всі елементи розв’язуючого стовпця, окрім РЕ, помножуються на (- λ) і результати записуються у нижньому правому куті відповідних ячійок таблиці.

5. У розв’язуючому рядку усі попередні значення, окрім РЕ, та у розв’язуючому стовпці усі нові, окрім РЕ, позначаються кутком.

6. Для кожного з елементів, які не належать ні розв’язуючому рядку, ні розв’язуючому стовпцю, у нижньому правому куті ячійки записується добуток виділених чисел розв’язуючого рядка і розв’язуючого стовпця, які знаходяться у тому ж рядку і тому ж стовпці, що і даний елемент.

7. Зводиться нова таблиця (таблиця №2) із заміною на , для чого елементи розв’язуючого рядка і стовпця заміняються числами, що знаходяться у нижніх правих кутках ячійок, які записуються у верхніх лівих кутах ячійок нової таблиці.

8. В інші ячійки, які не належать розв’язуючому рядку і стовпцю, у лівих верхніх кутках записують значення, які дорівнюють сумам чисел, що знаходяться у верхніх та нижніх кутах відповідних ячійок попередньої таблиці.

Таблиця №2

розв’язуючий стовпець (‍×-λ)

	Вільний член рівняння	Х4	Х2
F		- 4	-8 -8
X3	-40	0,6	0,4 0,4
X1	-100	- 1	1
X5	- 100	0	- 1 -1

9.3.3. Алгоритм визначення оптимального розв’язку ОЗЛП:

1. Якщо усі вільні члени в симплекс-таблиці, окрім рядка F, невід’ємні (додатки), а в ряду F усі коефіцієнти , окрім вільного члена, від’ємні, то оптимальний розв’язок досягнуто.

2. Якщо в рядку F є додатний елемент, а в стовпці немає жодного додатного елементу, то цільова функція не обмежена знизу і оптимального розв’язання не існує.

Розв’язуючи приклад далі послідовно застосовуються розглянуті алгоритми.

Вільний член третього рівня (таблиця №2) від’ємний (-100). У цьому рядку є від’ємний елемент .

В розв’язуючому стовпці із відношень

обираємо найменше .

Таким чином, у якості розв’язуючого елемента приймаємо .

Виконуючи алгоритм 9.3.2, одержуємо нове базисне рішення (таблиця №3).

Таблиця №3

	Вільний член рівняння	Х4	Х5
F	1200 + 800 = 2000	- 4 + 0 = -4	-8
X3	420 – 40 = 380	0,6 + 0 = 0,6	0,4
X1	300 – 100 = 200	-1 + 0 = -1
X2			-1

Аналізуючи дані таблиці №3, можна зробити висновки:

1. Так як усі вільні члени, окрім рядка F, додатні, а усі коефіцієнти цільової функції F від’ємні, то отриманий базисних розв’язок є оптимальним.

2. В результаті розрахунку одержали значення оптимальних потужностей КБ:

3. Капітальні вкладення при цьому складають:

грн.

9.4. Питання для самоконтролю:

1. Формулювання ОЗЛП?

2. Що називається областю допустимих рішень?

3. В якому випадку рішення ОЗЛП може бути не єдиним?

4. Сутність симплекс-методу?

5. Алгоритм знаходження розв’язуючого елементу?

6. Алгоритм перетворення таблиці шляхом заміни вільних і базисних змінних?

7. Алгоритм визначення оптимального розв’язку ОЗЛП?

Лекція №10

Транспортна задача.