Лекція 7. Визначення початкового опорного плану

Визначення початкового опорного плану

У розглянутому у попередній лекції прикладі усі непрямі обмеження задачі мали тип “ ”, і додаткові змінні визначали базис у початковій симплекс-таблиці. У тому разі, коли задача має непрямі обмеження різних типів, виникає проблема пошуку початкового базису. Розглянемо один з найпоширеніших методів розв’язування цієї проблеми, який називається методом штучної цільової функції.

Метод штучної цільової функції

Згідно з цим методом у кожне рівняння канонічної форми обмежень, що відповідає обмеженню вихідної задачі типу “ = ” або “ ” і, як наслідок, не містить базисної змінної у явному вигляді, уводять ще невід’ємну змінну, яку називають штучною. Штучна змінна з коефіцієнтом одиниця записується як доданок у ліву частину рівняння. Позначимо уведені штучні змінні як u₁, u₂, …, u_k. Після уведення штучних змінних система рівнянь-обмежень має базис у явному вигляді, але ця система не еквівалентна вихідній і співпадає з нею тільки при умові u₁ = u₂ = … = u_k = 0. Тому виникає задача пошуку невід’ємного розв’язку отриманої системи рівнянь з нульовими значеннями усіх штучних змінних.

Отримати такий розв’язок можна шляхом розв’язування допоміжної задачі лінійного програмування, обмеженнями якої є отримана система рівнянь при умові невід’ємності усіх змінних. Цільова функція допоміжної задачі має вигляд W = u₁ + u₂ + … + u_k і називається штучною цільовою функцією. Якщо існує шуканий розв’язок, то він дає оптимальне значення функції W і одночасно визначає базис для початкової симплекс-таблиці вихідної задачі. У тому разі, коли мінімум W більше нуля, шуканий розв’язок не існує, що свідчить про несумісність обмежень вихідної задачі.

Розглянемо приклад застосування методу штучної цільової функції.

F = 7x₁ + 5x₂ ® max,

2x₁ + x₂ £ 8,

4x₁ + 5x₂ = 20,

3x₁ + 8x₂ ³ 24,

x_1,x₂ ³ 0.

Канонічна форма обмежень має такий вигляд.

2x₁ + x₂ + x₃ = 8,

4x₁ + 5x₂ = 20,

3x₁ + 8x₂ - x₄ = 24,

x₁, …, x₄ ³ 0.

Після уведення штучних змінних отримуємо

2x₁ + x₂ + x₃ = 8,

4x₁ + 5x₂ + + x₅ = 20,

3x₁ + 8x₂ -x₄ +x₆ = 24,

x₁, …, x₆ ³ 0.

Дата добавления: 2014-01-13