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

Last updated
Save as PDF

Page ID: 67015

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

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

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

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

У цьому розділі ми вирішимо стандартні задачі мінімізації лінійного програмування за допомогою симплексного методу. Ще раз нагадаємо читачеві, що в стандартних задачах мінімізації всі обмеження мають вигляд$ax + by ≥ c$.

Процедура вирішення цих проблем була розроблена доктором Джоном Фон Нойманом. Вона передбачає вирішення пов'язаної проблеми, яка називається подвійною проблемою. До кожної проблеми мінімізації відповідає подвійна проблема. Рішення подвійної задачі використовується для пошуку рішення початкової задачі. Подвійна проблема - це проблема максимізації, яку ми навчилися вирішувати в останньому розділі. Ми спочатку вирішуємо подвійну задачу симплексним методом.

З остаточної симплексної таблиці ми потім витягуємо рішення початкової проблеми мінімізації.

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

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

Перетворіть наступну проблему мінімізації в її подвійну.

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

Рішення

Для досягнення поставленої мети ми спочатку висловлюємо нашу проблему як наступну матрицю.

\ [\ begin {масив} {cc|c}
1 & 2 & 40\\
1 & 1 & 30\
\ hline 12 & 16 & 0
\ кінець {масив}\ nonumber\]

Зверніть увагу, що ця таблиця виглядає як початкова симплексна таблиця без слабких змінних. Далі пишемо матрицю, стовпцями якої є рядки цієї матриці, а рядки - стовпці. Така матриця називається транспонуванням вихідної матриці. Отримуємо:

\ [\ begin {масив} {cc|c}
1 & 1 & 12\\
2 & 1 & 16\
\ hline 40 & 30 & 0
\ кінець {масив}\ nonumber\]

Наступна задача максимізації, пов'язана з вищевказаною матрицею, називається її подвійною.

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

Зверніть увагу, що ми вибрали змінні як y, а не х, щоб розрізнити дві проблеми.

Приклад$\PageIndex{2}$

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

Рішення

Наша проблема мінімізації полягає в наступному.

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

Тепер ми графуємо нерівності:

$imageedit_3_7200556551.png$

Ми побудували графік, затінювали область доцільності та позначили кутові точки. Кутова точка (20, 10) дає найнижче значення для цільової функції, і це значення дорівнює 400.

Тепер його подвійний:

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

Графуємо нерівності:

$imageedit_6_8472935815.png$

Знову ж таки, ми побудували графік, затінювали область доцільності та позначили кутові точки. Кутова точка (4, 8) дає найбільше значення для цільової функції, зі значенням 400.

Читач може розпізнати, що приклад$\PageIndex{2}$ вище збігається з Прикладом 3.1.1, у розділі 3.1. Це також та сама проблема, що і приклад 4.1.1 в розділі 4.1, де ми вирішили її симплексним методом.

Спостерігається, що мінімальне значення задачі мінімізації збігається з максимальним значенням задачі максимізації;$\PageIndex{2}$ у прикладі мінімум і максимум - 400. Це не збіг. Ми констатуємо принцип подвійності.

Принцип подвійності

Об'єктивна функція задачі мінімізації досягає свого мінімуму тоді і лише тоді, коли об'єктивна функція її дуалізації досягає свого максимуму. І коли вони це роблять, вони рівні.

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

Приклад$\PageIndex{3}$

Знайти розв'язання задачі мінімізації у прикладі$\PageIndex{1}$ шляхом розв'язання її дуальності за допомогою симплексного методу. Переписуємо нашу проблему.

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

Рішення

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

Нагадаємо, що вищевказану проблему ми вирішили симплексним методом в прикладі 4.1.1, розділ 4.1. Тому ми показуємо лише початкову та остаточну симплексну таблицю.

Початкова симплексна таблиця

\ [\ begin {масив} {ccccc|c}
\ математика {y} _1 &\ математика {y} _2 &\ математика {x} _ {1} &\ математика {x} _ {2} &\ математика {Z} &\\ математика {C}\\
1 & 1 & 1 & 0 & 0 & 0 & 12\
2 & 0 & 0 1 & 0 & 16\\
\\ лінія-40 & -30 & 0 & 0 & 1 & 0
\ кінець {масив}\ nonumber\]

Спостерігайте за важливою зміною. Тут наші основні змінні$\mathrm{y}_1$ і$\mathrm{y}_2$ і слабину змінні є$\mathrm{x}_1 and \mathrm{x}_2$.

Заключна симплексна таблиця читається наступним чином:

\ [\ begin {масив} {ccccc|c}
\ mathrm {y} _1 &\ mathrm {y} _2 &\ mathrm {x} _ {1} &\ mathrm {x} _ {2} &\\ mathrm {Z} &\\
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 &
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 4
\ 1\\ Лінія 0 & 0 & 20 & 10 & підсилювач; 1 & 400
\ кінець {масив}\ nonumber\]

Більш уважний погляд на цю таблицю показує, що$\mathrm{x}_2$ значення$\mathrm{x}_1$ і разом з мінімальним значенням для задачі мінімізації можна отримати з останнього рядка кінцевої таблиці. Ми виділили ці значення стрілками.

Повторно виставляємо розчин наступним чином:

Задача мінімізації має мінімальне значення 400 в кутовій точці (20, 10)

Зараз ми підсумуємо нашу дискусію.

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

Налаштуйте проблему.
Напишіть матрицю, рядки якої представляють кожне обмеження з цільовою функцією як нижній рядок.
Запишіть транспонування цієї матриці, змінюючи між собою рядки і стовпці.
Тепер напишіть подвійну проблему, пов'язану з транспонуванням.
Вирішити подвійну задачу за допомогою симплексного методу, вивченого в розділі 4.1.
Оптимальне рішення знайдено в нижньому рядку кінцевої матриці в стовпцях, відповідних змінним слабини, а мінімальне значення цільової функції збігається з максимальним значенням дуала.

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

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

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

Принцип подвійності

Принцип подвійності

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

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