19.Приклади побудови моделей економічних задач, що зводяться до задачі лінійного програмування (злп): задача оптимального розкрою

До задач лінійного програмування відносяться практично всі задачі опти-мального планування та керуванням виробництвом,до яких входить задача оптимального розкрою. Задача оптимального розкрою матеріалів. На підприємстві здійснюється розкрій m різних партій матеріалів у обсягах одиниць однакового розміру в кожній партії. Із матеріалів усіх партій потрібно виготовити максимальну кількість комплектів Z, у кожен з яких входить p різних видів окремих частин в кількості одиниць, враховуючи, що кожну одиницю матеріалу можна розкроїти на окремі частини n різними способами, причому у разі розкрою одиниці i-ої партії j-им способом отримуємо деталей r-го виду.Запишемо математичну модель задачі. Позначимо через — кількість одиниць матеріалу i-ої партії, що будуть розкроєні j-им способом. Тоді з i-ої партії за j-го способу розкрою отримаємо деталей r-го виду. З усієї ж i-ої партії у разі застосування до неї всіх n способів розкрою отримаємо деталей r-го виду, а з усіх m партій їх буде отримано . У кожен комплект має входити деталей, тому відношення визначає кількість комплектів, які можна виготовити з деталей r-го виду. Кількість повних комплектів для всіх видів деталей визначається найменшим з цих відношень.

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

Замінивши та їх значеннями, отримаємо p – 1 обмеження стосовно комплектів:

;

Враховуючи наявну кількість одиниць матеріалу в партіях, запишемо m обмежень щодо ресурсів: .

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

20.Геометрична інтерпретація симплексного методу

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

Допустимо, що початковий опорний план відповідає кутовій точці А. Тоді наступний крок симплексного методу приведе до точки Q, ( ), а в результаті ще однієї ітерації — до точки K, де лінійна функція набуває максимального значення. Проте, якщо початковим опорним планом буде точка В, то включення вектора до базису за критерієм приводить до того, що пряма проходитиме через точку С і алгоритм симплексного методу приведе до точок С, D, E, F, K, тобто для отримання оптимального плану необхідно буде виконати ще чотири ітерації.Отже, очевидно, що застосування симплексного методу не дає змоги одразу перейти від опорного плану (точки В) до оптимального (точки К). Фактично розв’язок отримують, рухаючись вздовж межі (ребер) простору розв’язків, причому не завжди такий шлях буде найкоротшим. Кількість ітерацій за реалізації симплексного алгоритму визначається вибором початкового опорного плану та кількістю кутових точок, що траплятимуться на шляху прямої .