існую в) функція має нескінченне число розвязків
Для розвязання задачі лінійного програмування можна користуватись ручним методом, графічнім або симплекс-методом. Ручний метод є й достатньо Простий и прімітівній. Основний его недолік це велика трудомісткість при розвязанні задачі. Чім больше змінніх тім важче розвязаті задачу лінійного програмування ручним методом.
Графічний метод розвязання й достатньо простий. Альо ВІН такоже НЕ Ефективний. Ним можна скористати позбав при наявності двох змінніх. У випадка трьох змінніх графічний розвязок становится Менш наочним, а при більшому чіслі змінніх - взагалі неможливим.
З переліченіх трьох методів симплекс метод є найбільш ефективна. ВІН дозволяє вірішіті будь-яку задачу при віконанні умови невіродженості. Оптимальний розвязок представляється однією з вершин багатогранника. Саме цею результат лежить в Основі симплекс-методу. Для поиска оптимуму звітність, в визначеному порядку переглянути невелика кількість вершин, вікорістовуючі Простий и Ефективний алгоритм послідовного покращення Значення цільової Функції, Який показано на малюнку 1.2.
Алгоритм розв язування задачі ЛП симплекс - методом має Такі етапи:
1.Обчіслюють елєменти рядка оцінок варіантів dj.
. Знаходять номер до вектора, что має максимальну по абсолютній велічіні додатного оцінку варіанта. Если ВСІ ОЦІНКИ варіанта відємні, то оптимальний план (переходять до 5). У протилежних випадка обчислюють вектор - стовпчік:
. Знаходять стрічку з номером ф, де. Если такого рядка немає, то задачу розвязаті Неможливо;
. Матрицю и вектор перетворюють в та відповідно, щоб вивести з базису вектор и Включити в нього вектор (Поліпшення плану) по формулах:
· елєменти стовпчік з номером А
;
· елєменти рядка з номером
;
· Інші елєменти и
· перейти до наступної ітерації (до п. 1);
5. Видають інформацію про оптимальний розв язок - значення невідоміх цільової Функції.
Рисунок 1.2 - Алгоритм решение задачі ЛП симплекс-методом
Порядок Виконання роботи проводять по Наступний етап:
· запісуємо цільову функцію;
· складаємо обмеження;
· обмеження У ФОРМІ нерівностей, вводячі додаткові змінні, перетворюємо у рівності, и вводяться в обмеження - рівності штучні перемінні;
· запісуємо матрицю обмежень и вектор цільової Функції, ВРАХОВУЮЧИ УСІ змінні у кожному рядку;
· вірішуємо задачу лінійного програмування на ЕОМ;
· у випадка нецілочісельного розв язання, с помощью методу гілок и між отрімуємо цілочісельній розв язок. Зі збільшенням номера розгалужень число Додатковий обмежень буде зростаті;
· среди отриманий цілочісельніх розв язків Обираємо оптимальний, з мінімальнім значенням цільової Функції;
· відповідно до індівідуального Завдання знаходимо необхідну залежність и відображаємо у вігляді графічної або математичної МОДЕЛІ.
1.2 аналітично-розрахунковий частина
У курсовій работе поставлено завдання Вибори оптимального складу ЗАСОБІВ ...
