3.2: Мінімізація додатків

Last updated
Save as PDF

Page ID: 67231

$ \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$, на відміну від форми$ax + by ≤ c$ для стандартної задачі максимізації. В результаті здійсненне рішення поширюється на невизначений термін до верхнього правого кута першого квадранта, і є необмеженим. Але це не викликає занепокоєння, оскільки для мінімізації об'єктивної функції лінія, пов'язана з об'єктивною функцією, рухається до початку, а критична точка, яка мінімізує функцію, найближча до походження.

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

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

В університеті професор Саймонс хоче працевлаштувати двох людей, Джона та Мері, для оцінки робіт для своїх занять. Джон є аспірантом і може оцінювати 20 робіт на годину; Джон заробляє $15 на годину для оцінки робіт. Мері є пост-докторантом і може оцінювати 30 робіт на годину; Мері заробляє $25 на годину для оцінювання робіт. Кожен повинен бути працевлаштований принаймні одну годину на тиждень, щоб виправдати свою зайнятість.
Якщо професор Саймонс має щонайменше 110 робіт, які потрібно оцінювати щотижня, скільки годин на тиждень він повинен найняти кожну людину, щоб мінімізувати витрати?

Рішення

Вибираємо змінні наступним чином:

Нехай$x$ = Кількість годин на тиждень Джон зайнятий.

і$y$ = Кількість годин на тиждень Мері працевлаштована.

Об'єктивною функцією є

\[C = 15x + 25y \nonumber \]

Той факт, що кожен повинен працювати щонайменше одну годину щотижня призводить до наступних двох обмежень:

\ [\ begin {масив} {l}
x\ geq 1\
y\ geq 1
\ end {масив}\ nonumber\]

Оскільки Джон може оцінювати 20 робіт на годину, а Мері 30 паперів на годину, і є щонайменше 110 паперів, які будуть оцінені на тиждень, ми отримуємо

\[20x + 30y ≥ 110 \nonumber \]

Те, що$x$ і$y$ є ненегативними, ми отримуємо

\[x ≥ 0 \text{, and } y ≥ 0. \nonumber \]

Проблема була сформульована наступним чином.

\ [\ begin {масив} {ll}
\ textbf {Мінімізувати} &\ mathrm {C} =15\ mathrm {x} +25
\ mathrm {y}\\ textbf {За умови:}
&\ mathrm {x}\ geq 1\\\
mathrm {x} +30\ математика {y}\ gea 110\\
&\ mathrm {x}\ geq 0; \ mathrm {y}\ geq 0
\ кінець {масив}\ номер\]

Щоб вирішити задачу, графуємо обмеження наступним чином:

$Приклад 3.2.1.PNG$

Знову ж таки, ми затінювали область техніко-економічного обґрунтування, де всі обмеження задовольняються.

Якщо ми використовували тестову точку (0,0), яка не лежить на жодному з обмежень, ми спостерігаємо, що (0, 0) не задовольняє жодне з обмежень$x ≥ 1$,$y ≥ 1$,$20x + 30y ≥ 110$. Таким чином, все затінення для області доцільності лежить на протилежній стороні обмежувальних ліній від точки (0,0).

Крім того, ми могли б використовувати тестову точку (4,6), яка також не лежить на жодній з ліній обмеження. Ми виявимо, що (4,6) задовольняє всі обмеження нерівності. Отже, все затінення для області доцільності лежить на тій же стороні обмежувальних ліній, що і точка (4,6).

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

критичні точки	Дохід
(1, 3)	15 (1) + 25 (3) = 90 доларів
(4, 1)	15 (4) + 25 (1) = $85

Точка (4, 1) дає найменшу вартість, і ця вартість становить 85 доларів. Тому ми робимо висновок, що для того, щоб мінімізувати витрати на оцінку, професор Саймонс повинен наймати Джона 4 години на тиждень, а Мері 1 годину на тиждень за ціною 85 доларів на тиждень.

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

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

	МАКАРОНИ	ТОФУ
БІЛОК	8 г	16г
ВУГЛЕВОДІВ	60 г	40 г
ВІТАМІН С	2г	2г
ХОЛЕСТЕРИН	60 мг	50 мг

Рішення

Вибираємо змінні наступним чином.

Нехай$x$ = Кількість днів пан Хамер їсть макарони.

і$y$ = Кількість днів, які містер Хамер їсть Тофу.

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

\[C = 60x + 50y \nonumber \]

Обмеження, пов'язане із загальною кількістю білка, що забезпечується обома прийомами їжі, є

\[8x + 16y ≥ 200 \nonumber \]

Аналогічно виходять два обмеження, пов'язані із загальною кількістю вуглеводів і вітамінів, і вони

\ [\ begin {масив} {l}
60 x+40 y\ geq 960\\
2 x+2 y\ geq 40
\ end {масив}\ nonumber\]

Обмеження, які стверджують, що x і y є невід'ємними, є

\[x ≥ 0 \text{, and } y ≥ 0 \nonumber. \nonumber \]

Узагальнюємо всю інформацію наступним чином:

\ [\ begin {масив} {ll}
\ textbf {Мінімізувати} &\ математика {C} =60\ математика {x} +50\ mathrm {y}\
\ textbf {За умови:} & 8\ mathrm {x} +16\ mathrm {y}\ geq 200\\
& 60\ mathrm {x} +40\ mathrm {y}\ geq 960\\
& 2\ mathrm {x} +2\ матрм {y}\ geq 40\\
&\ mathrm {x}\ geq 0;\ mathrm {y}\ geq 0
\ end {масив}\ номер\]

Щоб вирішити проблему, ми графуємо обмеження та затінюємо область техніко-економічного обґрунтування.

$Приклад 3.2.3.PNG$

Ми затінювали необмежену область техніко-економічного обґрунтування, де всі обмеження задовольняються.

Для мінімізації цільової функції знаходимо вершини області техніко-економічного обґрунтування. Ці вершини є (0, 24), (8, 12), (15, 5) і (25, 0). Щоб мінімізувати рівень холестерину, ми замінимо ці точки в об'єктивну функцію, щоб побачити, яка точка дає нам найменше значення. Результати наведені нижче.

критичні точки	Дохід
(0, 24)	60 (0) + 50 (24) = 1200
(8, 12)	60 (8) + 50 (12) = 1080
(15, 5)	60 (15) + 50 (5) = 1150
(25, 0)	60 (25) + 50 (0) = 1500

Точка (8, 12) дає найменший рівень холестерину, який становить 1080 мг. Це говорить, що на кожні 20 прийомів їжі професор Хамер повинен їсти макарони 8 днів, а тофу 12 днів.

Ми повинні знати, що в деяких випадках лінійна програма може не мати оптимального рішення.

Лінійна програма може не мати оптимального рішення, якщо немає області техніко-економічного обґрунтування. Якщо обмеження нерівності несумісні, на графіку може не бути області, яка задовольняє всім обмеженням. Якщо лінійна програма не має здійсненного рішення, що задовольняє всім обмеженням, то вона не може мати оптимального рішення.
Лінійна програма може не мати оптимального рішення, якщо область техніко-економічного обґрунтування необмежена.
- Дві лінійні програми мінімізації, які ми розглядали, мали необмежені регіони техніко-економічного обґрунтування. Область техніко-економічного обґрунтування була обмежена обмеженнями з деяких сторін, але не була повністю обмежена обмеженнями. Обидві проблеми мінімізації мали оптимальні рішення.
- Однак, якби ми розглянули проблему максимізації з подібною необмеженою областю техніко-економічного обґрунтування, лінійна програма не мала б оптимального рішення. Незалежно від того, які значення x і y були обрані, ми завжди могли знайти інші значення$y$,$x$ і це призведе до більш високого значення для цільової функції. Іншими словами, якщо значення цільової функції може бути збільшено без обмежень в лінійній програмі з необмеженою посильною областю, оптимального максимального рішення не існує.

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

Мінімізація задач лінійного програмування

Напишіть об'єктивну функцію.
Напишіть обмеження.
1. Для стандартних задач лінійного програмування мінімізації обмеження мають вигляд:$ax + by ≥ c$
2. Оскільки змінні невід'ємні, включають обмеження:$x ≥ 0$;$y ≥ 0$.
Графік обмежень.
Затіньте область доцільності.
Знайдіть кутові точки.
Визначте кутову точку, яка дає мінімальне значення.
1. Це можна зробити, знайшовши значення цільової функції в кожній кутовій точці.
2. Це також можна зробити, перемістивши лінію, пов'язану з цільовою функцією.
3. Існує ймовірність того, що проблема не має рішення

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

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

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