4.2: Максимізація за допомогою симплексного методу

Цілі навчання

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

1. Визначте та налаштуйте лінійну програму у стандартній формі максимізації
2. Перетворення обмежень нерівності в рівняння за допомогою слабких змінних
3. Налаштуйте початкову симплексну таблицю за допомогою цільової функції та рівнянь слабкості
4. Знайдіть оптимальну симплексну таблицю, виконуючи поворотні операції.
5. Визначте оптимальне рішення з оптимальної симплексної таблиці.

В останньому розділі ми використовували геометричний метод для вирішення задач лінійного програмування, але геометричний підхід не спрацює для задач, які мають більше двох змінних. У реальних життєвих ситуаціях завдання лінійного програмування складаються буквально з тисяч змінних і вирішуються комп'ютерами. Ми можемо вирішити ці проблеми алгебраїчно, але це буде не дуже ефективно. Припустимо, нам дали проблему з, скажімо, 5 змінних і 10 обмежень. Вибравши всі комбінації п'яти рівнянь з п'ятьма невідомими, ми змогли знайти всі кутові точки, перевірити їх на доцільність і придумати рішення, якщо воно існує. Але біда в тому, що навіть для проблеми з такою кількістю змінних ми отримаємо більше 250 кутових точок, і тестування кожної точки буде дуже нудно. Тому нам потрібен метод, який має систематичний алгоритм і може бути запрограмований для комп'ютера. Метод повинен бути досить ефективним, щоб нам не довелося оцінювати цільову функцію в кожній кутовій точці. У нас якраз такий метод, і називається він симплексним методом.

Симплексний метод був розроблений під час Другої світової війни доктором Джорджем Данцигом. Його лінійні моделі програмування допомогли союзним військам вирішити проблеми з транспортуванням та плануванням. У 1979 році радянський вчений на ім'я Леонід Хачян розробив метод під назвою еліпсоїдний алгоритм, який повинен був бути революційним, але, як виявилося, він не кращий за симплексний метод. У 1984 році Нарендра Кармаркар, науковий співробітник AT&T Bell Laboratories, розробив алгоритм Кармаркара, який, як було доведено, в чотири рази швидше, ніж симплексний метод для певних проблем. Але симплексний метод все ж найкраще працює для більшості проблем.

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

Щоб дізнатися симплексний метод, спробуємо досить нетрадиційний підхід. Перерахуємо спочатку алгоритм, а потім працюємо над проблемою. Ми обґрунтовуємо міркування кожного кроку під час процесу. Ретельне обгрунтування виходить за рамки цього курсу.

Почнемо з прикладу, який ми вирішили в останньому розділі графічним методом. Це дасть нам деяке розуміння симплексного методу і в той же час дасть нам можливість порівняти кілька можливих рішень, які ми отримали раніше графічним методом. Але спочатку перерахуємо алгоритм для симплексного методу.

СИМПЛЕКСНИЙ МЕТОД

1. Налаштуйте проблему. Тобто запишіть об'єктивну функцію і обмеження нерівності.
2. Перетворіть нерівності в рівняння. Це робиться шляхом додавання однієї змінної слабкості для кожної нерівності.
3. Побудувати початкову симплексну таблицю. Напишіть об'єктивну функцію як нижній ряд.
4. Найбільш негативний запис у нижньому рядку визначає стовпець зведення.
5. Обчисліть коефіцієнти. Найменший коефіцієнт ідентифікує рядок. Елемент у перетині стовпчика, визначеного на кроці 4, і рядка, визначеного на цьому кроці, ідентифікується як шарнірний елемент. Коефіцієнти обчислюються шляхом ділення крайнього правого стовпця на ідентифікований стовпець у кроці 4. Коефіцієнт, який є нулем, або від'ємним числом, або який має нуль у знаменнику, ігнорується.
6. Виконайте поворот, щоб зробити всі інші записи в цьому стовпці нульовим. Робиться це так само, як ми робили з методом Гауса-Джордана.
7. Коли в нижньому рядку більше немає негативних записів, ми закінчили; інакше ми знову починаємо з кроку 4.
8. Прочитайте свої відповіді. Отримати змінні, використовуючи стовпці з 1 і 0. Всі інші змінні дорівнюють нулю. Максимальне значення, яке ви шукаєте, з'явиться в правому нижньому куті.

Тепер ми використовуємо симплексний метод для вирішення Приклад 3.1.1, вирішений геометрично в розділі 3.1.

Приклад\(\PageIndex{1}\)

Нікі має дві роботи за сумісництвом, роботу I та роботу II. Вона ніколи не хоче працювати більше, ніж загалом 12 годин на тиждень. Вона визначила, що на кожну годину, яку вона працює в Іові І, їй потрібно 2 години часу на підготовку, а на кожну годину, яку вона працює на Іові, їй потрібна одна година часу на підготовку, і вона не може витратити більше 16 годин на підготовку. Якщо вона заробляє 40 доларів на годину на роботі I та 30 доларів на годину на роботі II, скільки годин вона повинна працювати на тиждень на кожній роботі, щоб максимізувати свій дохід?

Рішення

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

КРОК 1. Налаштуйте проблему. Напишіть об'єктивну функцію та обмеження.

Так як симплексний метод використовується для задач, які складаються з безлічі змінних, то використовувати змінні\(x\) непрактично\(z\) і т.п. ми використовуємо символи\(x_1\),\(x_2\),\(x_3\), і так далі.\(y\)

Нехай

• \(x_1\)= Кількість годин на тиждень Нікі буде працювати на Job I і
• \(x_2\)= Кількість годин на тиждень Нікі працюватиме на Job II.

Прийнято вибирати змінну, яку слід максимізувати як\(Z\).

Проблема сформульована так само, як ми це робили в останньому розділі.

\ [\ begin {масив} {ll}
\ textbf {Максимізувати} &\ mathrm {Z} =40\ математика {x} _ {1} +30\ mathrm {x} _ {2}
\\ textbf {За умови:} &\ mathrm {x} _ {1} +\ mathrm {x} _ {2}\ leq 12\\
& 2\ математика {x} _ {1} +\ математика {x} _ {2}\ leq 16\\
&\ математика {x} _ {1}\ geq 0;\ mathrm {x} _ {2}\ geq 0
\ кінець {масив}\ nonumber\]

КРОК 2. Перетворіть нерівності в рівняння. Це робиться шляхом додавання однієї змінної слабкості для кожної нерівності.

Наприклад, щоб\(x_1 + x_2 ≤ 12\) перетворити нерівність у рівняння, ми додаємо невід'ємну змінну\(y_1\), і отримуємо

\[x_1 + x_2 + y_1 = 12 \nonumber \]

Тут змінна\(y_1\) підхоплює слабину, і вона являє собою суму, на яку не\(x_1 + x_2\) вистачає 12. У цій проблемі, якщо Нікі працює менше 12 годин, скажімо 10, то\(y_1\) це 2. Пізніше, коли ми зчитуємо остаточне рішення з симплексної таблиці, значення змінних слабкості ідентифікують невикористані суми.

Переписуємо об'єктивну функцію\(Z = 40x_1 + 30x_2\) як\(- 40x_1 - 30x_2 + Z = 0\).

Після додавання змінних слабкості наша проблема читає

\ [\ begin {масив} {ll}
\ текст {Об'єктивна функція} & - 40x_1 - 30x_2 + Z = 0
\\\ текст {За умови обмежень:} & x_1 + x_2 + y_1 = 12\\
& 2x_1 + x_2 + y_2 = 16\\
& x1 ≥ 0; x2 ≥ 0
\ end {масив}\ nonumber\]

КРОК 3. Побудувати початкову симплексну таблицю. Кожне обмеження нерівності з'являється у своєму рядку. (Ненегативні обмеження не відображаються як рядки в симплексної таблиці.) Напишіть об'єктивну функцію як нижній ряд.

Тепер, коли нерівності перетворюються на рівняння, ми можемо представити задачу в доповнену матрицю, яка називається початковою симплексною таблицею наступним чином.

Тут вертикальна лінія відокремлює ліву частину рівнянь від правого боку. Горизонтальна лінія відокремлює обмеження від цільової функції. Права частина рівняння представлена стовпцем C.

Читачеві необхідно зауважити, що останні чотири стовпці цієї матриці виглядають як кінцева матриця для розв'язання системи рівнянь. Якщо довільно вибрати\(x_1 = 0\) і\(x_2 = 0\), то отримаємо

\ [\ лівий [\ почати {масив} {ccccc}
y_ {1} & y_ {2} & Z & | & C\\
1 & 0 & 0 & | & 12\\
0 & 1 & 0 & | & 16\\
0 & 0 & 0 & 1 & | & 0
\ кінець {масив}\ праворуч]\ nonumber\]

який читає

\[y_1 = 12 \quad y_2 = 16 \quad Z = 0 \nonumber \]

Рішення, отримане шляхом довільного присвоєння значень деяким змінним з подальшим рішенням для інших змінних, називається базовим рішенням, пов'язаним з таблицею. Отже, вищевказане рішення є основним рішенням, пов'язаним з початковою симплексною таблицею. Ми можемо позначити базову змінну рішення праворуч від останнього стовпця, як показано в таблиці нижче.

КРОК 4. Найбільш негативний запис у нижньому рядку визначає стовпець зведення.

Найбільш негативним записом в нижньому рядку є -40; тому стовпець 1 ідентифікується.

Питання Чому ми вибираємо найбільш негативний запис в нижньому ряду?

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

Симплексний метод починається в кутовій точці, де всі основні змінні, змінні, які мають такі символи\(x_1\),\(x_2\) як\(x_3\) і т.д., дорівнюють нулю. Потім він переміщається від кутової точки до сусідньої кутової точки, завжди збільшуючи значення цільової функції. У випадку з\(Z = 40x_1+ 30x_­2\) об'єктивною функцією буде більше сенсу збільшувати значення,\(x_1\) ніж\(x_2\). Змінна\(x_1\) представляє кількість годин на тиждень Нікі працює на роботі I. Оскільки робота I платить 40 доларів на годину, на відміну від Job II, яка платить лише 30 доларів, змінна\(x_1\) збільшить цільову функцію на 40 доларів за одиницю збільшення змінної\(x_1\).

КРОК 5. Обчисліть коефіцієнти. Найменший коефіцієнт ідентифікує рядок. Елемент у перетині стовпчика, визначеного на кроці 4, і рядка, визначеного на цьому кроці, ідентифікується як шарнірний елемент.

Слідуючи алгоритму, щоб обчислити частку, розділимо записи в крайньому правому стовпці на записи в стовпці 1, виключаючи запис в нижньому рядку.

Найменший з двох коефіцієнтів, 12 і 8, - це 8. Тому ряд 2 ідентифікується. Перетин стовпця 1 і рядка 2 - це запис 2, який був виділений. Це наш стрижневий елемент.

Питання: Чому ми знаходимо коефіцієнти, і чому найменший коефіцієнт ідентифікує рядок?

Відповідь. Коли ми вибираємо найбільш негативний запис в нижньому ряду, ми намагаємося збільшити значення об'єктивної функції шляхом введення змінної\(x_1\). Але ми не можемо вибрати жодної цінності для\(x_1\). Чи можемо ми дозволити\(x_1 = 100\)? Однозначно ні! Це тому, що Нікі ніколи не хоче працювати більше 12 годин на обох роботах разом узятих:\(x_1 + x_2 ≤ 12\). Чи можемо ми дозволити\(x_1 = 12\)? Знову ж таки, відповідь - ні, тому що час підготовки до Іова I вдвічі перевищує час, витрачений на роботу. Так як Нікі ніколи не хоче витрачати на підготовку більше 16 годин, то максимальний час, який вона може працювати, становить 16 ÷ 2 = 8.

Тепер ви бачите мету обчислення коефіцієнтів; використання коефіцієнтів для ідентифікації стрижневого елемента гарантує, що ми не порушуємо обмежень.

Питання: Чому ми ідентифікуємо стрижневий елемент?

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

Змінна, одиниці якої додаються, називається вхідною змінною, а змінна, одиниці якої замінюються, називається змінною, що відходить. Вхідна змінна в наведеній вище таблиці є\(x_1\), і вона була ідентифікована самим негативним записом в нижньому рядку. Відходить змінна\(y_2\) була ідентифікована найменшим з усіх коефіцієнтів.

КРОК 6. Виконайте поворот, щоб зробити всі інші записи в цьому стовпці нульовим.

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

Для отримання нуля в записі першого над шарнірним елементом множимо другий ряд на -1 і додаємо його в рядок 1. Ми отримуємо

Щоб отримати нуль в елементі нижче стрижня множимо другий ряд на 40 і додаємо його до останнього ряду.

Тепер визначимо основне рішення, пов'язане з цією таблицею. Довільно вибираючи\(x_2 = 0\) і\(y_2 = 0\), отримуємо\(x_1 = 8\)\(y_1 = 4\), і\(z = 320\). Якщо ми запишемо доповнену матрицю, ліва сторона якої - матриця зі стовпцями, які мають один 1 і всі інші записи нулі, ми отримаємо наступну матрицю, яка говорить про те ж саме.

\ [\ ліворуч [\ почати {масив} {ccccc}
\ математика {x} _ {1} &\ mathrm {y} _1 &\ mathrm {Z} & | &\
mathrm {C}\\ 0 & 0 & 0 & 4\
1 & 0 & 0 & 8\
0 & 0 & 0 & 0 & 1 | & 320
\ кінець {масив}]\ номер\]

Ми можемо відновити рішення, пов'язане з цією матрицею як\(x_1 = 8\),\(x_2 = 0\),\(y_1 = 4\),\(y_2 = 0\) і\(z = 320\). На цьому етапі гри йдеться про те, що якщо Нікі працює 8 годин на Job I, а годин у Job II немає, її прибуток Z складе 320 доларів. Нагадаємо з прикладу 3.1.1 в розділі 3.1, що (8, 0) була однією з наших кутових точок. Тут\(y_1 = 4\) і\(y_2 = 0\) означає, що їй залишиться 4 години робочого часу і без часу на підготовку.

КРОК 7. Коли в нижньому рядку більше немає негативних записів, ми закінчили; інакше ми знову починаємо з кроку 4.

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

Робимо шарнірний елемент 1, множивши ряд 1 на 2, і отримуємо

Тепер, щоб зробити всі інші записи як нулі в цьому стовпці, ми спочатку множимо рядок 1 на -1/2 і додаємо його до рядка 2, а потім множимо рядок 1 на 10 і додаємо його до нижнього рядка.

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

Питання Чому ми закінчили, коли в нижньому рядку немає негативних записів?

Відповідь. Відповідь лежить в нижньому ряду. Нижній ряд відповідає рівнянню:

\ [\ begin {масив} {l}
0 x_ {1} +0 x_ {2} +20 y_ {1} +10 y_ {2} +Z = 400\ квадратний\ текст {або}\\
z=400-20 y 1-10 y 2
\ end {масив}\ nonumber\]

Оскільки всі змінні невід'ємні, найвища величина\(Z\) може коли-небудь досягти 400, і це станеться тільки тоді, коли\(y_1\) і\(y_2\) дорівнюють нулю.

КРОК 8. Прочитайте свої відповіді.

Ми зараз зачитуємо наші відповіді, тобто визначаємо базове рішення, пов'язане з остаточною симплексної таблицею. Знову ж таки, ми дивимося на стовпці, які мають 1 і всі інші записи нулі. Так як стовпці з маркуванням\(y_1\) і не\(y_2\) є такими стовпцями, ми довільно вибираємо\(y_1 = 0\), і\(y_2 = 0\), і отримуємо

\ [\ left [\ begin {масив} {ccccc}
\ mathrm {x} _ {1} &\ mathrm {x} _ {2} &\ mathrm {Z} & | &\\
mathrm {C}\\ 0 &
1 & 0 & 0 & 0 & & 4\
0 & 0 & 1 & 400
\ кінець {масив}\ праворуч] \ номер\]

Матриця читає\(x_1 = 4\),\(x_2= 8\) і\(z = 400\).

Остаточне рішення говорить, що якщо Нікі працює 4 години на Job I і 8 годин на Job II, вона максимізує свій дохід до 400 доларів. Оскільки обидві слабкі змінні дорівнюють нулю, це означає, що вона витратила б весь робочий час, а також час підготовки, і жоден не залишиться.

­