мо напрям вектора. Вектор нормалі показує напрямок руху функції з многоугольнику. p> Тепер побудуємо цільову функцію. Цільову функцію можна зобразити у вигляді сітки паралельних прямих, достатньо для побудови прирівняти цільову функцію до будь-якого значенням і побудувати пряму (; (4; 0); (0, 2)). Та точка, через яку пройде цільова функція при переміщенні уздовж вектора нормалі виявиться останньою у многокутнику буде відповіддю. Ця туга з координатами (2, 3). Отримуємо відповідь:. Для отримання оптимального плану підставимо координати в цільову функцію і отримаємо:, оптимальний план:. br/>
Завдання № 2. Вирішити транспортну задачу
Вирішити транспортну задачу. Задані потужності постачальників аi (i = 1,2,3), ємності споживачів bj (j = 1,2,3) і матриця вартостей перевезень одиниці продукції від кожного постачальника кожному споживачеві. Потрібно знайти план перевезень, при якому сумарні транспортні витрати будуть найменшими. p> Вихідні дані:
Таблиця № 5 - Вихідні дані
ПотребителиB1B2B3Поставщики142022A150389A218345А312276
Вирішити завдання можна в тому випадку якщо завдання закрита, тобто має виконувати рівність: 50 +18 +12 = 14 +20 +22, виходить 8056; введемо додаткового споживача
-56 = 24.
Таблиця № 6 - Введення додаткового споживача
Складемо вихідний план перевезень Х 1 (Малюнок 4) методом В«північно-західного кутаВ», розподіляючи потужності постачальників по порядком між споживачами, так щоб кожна перевезення було максимально можливою.
План перевезень оформимо у вигляді таблиці, розділеної на клітини. У центрі кожної клітини плану помістимо перевезення, а в правому верхньому кутку - вартість перевезення одиниці продукції. В клітини, відповідні нульовим перевезень, нулі не вписуємо, залишаючи їх порожніми. У такому випадку план Х1 буде містити не більше, ніж m + n-1 позитивних перевезень або зайнятих клітин, де m - число постачальників, n - число споживачів. Інші компоненти плану Х1, відповідні нульовим перевезень, будемо називати вільними клітинами. Якщо число зайнятих клітин K = m + n -1, то план перевезень називається невиродженим, якщо K Підрахуємо сумарну вартість перевезень за планом Х1:
В
Перевіримо план Х1 (Малюнок 4) на оптимальність. Знайдемо потенціали постачальників і потенціали споживачів. br/>В
Рисунок 4 - План Х1 (План)
За умовою для зайнятих клітин:
В В
Один з потенціалів завжди задається довільно, задамо. Тоді з системи отримаємо,,,,,,. Ці потенціали корисно записати праворуч і знизу від плану. p> За умовою для вільних клітин:
В В
Підставами потенціали в нерівності, отримаємо:
; 4> 0 ; -1 <3; 4 = 4
; -4 <2; 4 <7; 5 <6
Ми бачимо, що не виконується одна нерівність
В
Отже, план м...