>Лінійна оптимізація>Як застосовувати метод лінійки для лінійної оптимізації

Як застосовувати метод лінійки для лінійної оптимізації

Тут ти дiзнаєшся, як застосовувати метод лiнiйки для лiнiйної оптимiзацiї.

Правило

Метод лiнiйки

1.

Склади нерiвностi на основi завдання. Оскiльки йдеться про кiлькiсть одиниць, природно сказати, що

x \geq 0

y \geq 0

, тому що неможливо отримати вiд’ємну кiлькiсть одиниць.

2.

Розв’яжи нерiвностi для

y

, щоб вони отримали вигляд функцiй

y (x)

3.

Побудуй графiки цих функцiй у системi координат. Через те, що

x \geq 0

y \geq 0

, потрiбно враховувати лише перший квадрант.

4.

Познач область, оточену графiками!

5.

Знайди рiвняння для прямих цiльової функцiї. Використовуй цiльову функцiю, яка позначає те, що треба оптимiзувати: прибуток, дохiд тощо. Цiльову функцiю можна знайти шляхом додавання «цiни за одиницю», помноженої на «кiлькiсть одиниць» для всiх типiв товару, якi ми маємо. Функцiя матиме такий вигляд:

Z (x, y) = A x + B y,

де $A$ — це цiна товару, $x$ одиниць якого було продано, а $B$ — це цiна товару, $y$ одиниць якого було продано.

Мiняємо мiсцями $Z (x, y)$ з константою $K$ . Розв’язуємо рiвняння для $y$ , щоб отримати лiнiйну функцiю, яку можна перемiщувати:

\begin{array}{l} Z (x, y) & = A x + B y \\ K & = A x + B y \\ K - A x & = B y \\ B y & = K - A x \\ y & = \frac{K}{B} - \frac{A}{B} x \\ y & = - \frac{A}{B} x + \frac{K}{B} \end{array}

Значення тут має лише кутовий коефiцiєнт функцiї $- \frac{A}{B}$ . Вiльний член постiйно змiнюється, тому що ми змiнюємо значення $K$ , щоб змiщувати лiнiю назовнi системи координат.

6.

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

7.

Зчитуємо координати цiєї точки. Це оптимальна точка.

8.

Знаходимо прибуток/дохiд, пiдставивши координати оптимальної точки в

Z (x, y)

Приклад 1

Фабрика, що випускає фiрмову продукцiю, виготовлятиме чоловiчi сорочки та спiдницi для дизайнера Тома Форда. Обидва товари вироблятимуться з кашемiру та шовку. На сорочку йде два вiдрiзи кашемiру та один вiдрiз шовку. На спiдницю йде один вiдрiз кашемiру та три вiдрiзи шовку. На фабрицi є 200 вiдрiзiв кашемiру та 300 вiдрiзiв шовку. Сорочка коштує $$ 295$ , а спiдниця — $$ 450$ . Скiльки спiдниць i чоловiчих сорочок потрiбно виробити, щоб збiльшити дохiд фабрики, i яким буде цей дохiд?

Пункт 1

Спершу задаємо обмеження в текстi завдання у виглядi нерiвностей. Нехай $x$ — це кiлькiсть вироблених чоловiчих сорочок, а $y$ — кiлькiсть вироблених спiдниць. Кашемiр та шовк потрiбно розподiлити мiж сорочками та спiдницями. Отримуємо такi нерiвностi:

Кiлькiсть сорочок, якi ми виробляємо, може становити 0 сорочок i бiльше. Отже,
$x \geq 0 .$
Кiлькiсть спiдниць, якi ми виробляємо, може становити 0 спiдниць i бiльше. Отже,
$y \geq 0 .$
Тепер складаємо нерiвнiсть для наявного кашемiру. На сорочку йде два вiдрiзи, а на спiдницю — один. Один рулон загалом вмiщує $200$ вiдрiзiв. Отримуємо
$2 x + y \leq 200 .$
Потiм складаємо нерiвнiсть для наявного шовку. На сорочку йде один вiдрiз, а на спiдницю — три. Один рулон вмiщує $300$ вiдрiзiв шовку. Отримуємо
$x + 3 y \leq 300 .$

У кiнцевому пiдсумку маємо систему нерiвностей:

\begin{align} x & \geq 0 & (1) \\ y & \geq 0 & (2) \\ 2 x + y & \leq 200 & (3) \\ x + 3 y & \leq 300 & (4) \end{align}

Пункт 2

Тепер потрiбно розв’язати нерiвностi щодо $y$ . Спочатку розв’язуємо нерiвнiсть (3):

\begin{array}{l} 2 x + y & \leq 200 \\ y & \leq 200 - 2 x \end{array}

Нерiвнiсть (4):

\begin{array}{l} x + 3 y & \leq 300 \\ 3 y & \leq 300 - x | : 3 \\ y & \leq 100 - \frac{1}{3} x \end{array}

З iншими двома нерiвностями нiчого робити не потрiбно.

Пункт 3 i 4

Зобразимо двi нерiвностi у виглядi графiкiв у системi координат i позначимо область, у якiй вони перетинаються. Як вiдомо, нас цiкавить лише перший квадрант, оскiльки i $x$ , i $y$ бiльшi або дорiвнюють 0. Отримуємо таку фiгуру:

Приклад лiнiйної оптимiзацiї методом лiнiйки 1

Пункт 5

Знаходимо для цiєї фiгури оптимальну точку. Як ми знаємо, це одна з точок у межах позначеної областi, в якiй графiки перетинаються мiж собою або перетинають осi. Якщо використовується метод лiнiйки, потрiбно знайти вираз для цiльової функцiї $Z (x, y) = A x + B y$ . Як вiдомо, чоловiча сорочка коштує $ $295$ , а спiдниця коштує $ $450$ . Пiдставляємо цiни $A$ i $B$ у вираз i розв’язуємо для $y$ . Отримуємо

\begin{array}{l} Z (x, y) & = 295 x + 450 y \\ K & = 295 x + 450 y \\ 450 y & = K - 295 x | : 450 \\ y & = \frac{K}{450} - \frac{295}{450} x \\ y & \approx - 0.66 x - \frac{K}{450} . \end{array}

Пункт 6

Через те, що член з $K$ (вiльний член) не грає ролi, коли ми виштовхуємо лiнiю назовнi першого квадранта, можна обрати для нього будь-яке значення. Доцiльно почати з вибору значення на осi $y$ , яке перебуває в межах позначеної областi. На рисунку нижче вiльний член було обрано рiвним $80$ . Функцiя має такий вигляд:

Приклад лiнiйної оптимiзацiї методом лiнiйки 2

Помiщаємо лiнiйку на чорну лiнiю (лiнiя: $y = - 0.66 x + 80$ ) i проводимо нею паралельно позначенiй областi. Зрештою опинимося в ситуацiї, коли край лiнiйки торкається позначеної областi лише в однiй точцi. Ця точка є точкою перетину мiж двома графiками або графiком i вiссю, i є оптимальною точкою.

Приклад лiнiйної оптимiзацiї методом лiнiйки 3

Пункт 7

Зчитуємо координати точки i з’ясовуємо, що $B = (60, 80)$ . Це означає, що фабрицi потрiбно виробляти $60$ чоловiчих сорочок i $80$ спiдниць, щоб збiльшити свiй дохiд.

Пункт 8

Знаходимо дохiд фабрики в оптимальнiй точцi, пiдставивши значення $x$ i $y$ , якi ми знайшли в Пункт 7, у цiльову функцiю. Це значення $x = 60$ , а $y = 80$ ; отримуємо

Z (60, 80) = 295 \cdot 60 + 450 \cdot 80 = 53 700 .

Фабрика заробляє $ $53 700$ , виробляючи $60$ чоловiчих сорочок i $80$ спiдниць. Це оптимальне виробництво, оскiльки пряма цiльової функцiї перетнула крайню точку позначеної областi.

Бажаєш дізнатися більше?ЗареєструйсяЦе безплатно!

Попередня стаття

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

Повернутися