Завдання назівають «основних» або «стандартнийїм » в лінійному програмуванні.
2. Симплекс-метод
Завдання лінійного програмування в канонічній ФОРМІ широко пошірені в інженерній практіці, и для їх Вирішення розроблено велика група методів, основної з якіх - симплекс-метод. Розглянемо постановку и решение задачі лінійного програмування в канонічній ФОРМІ.
Завдання розглядатіметься У ФОРМІ, яка назівається канонічною. Відомо, что путем Введення Додатковий обмежень и змінніх можна звесті до канонічної форми Завдання лінійного програмування, представлених в будь-якій ФОРМІ, зокрема в природній ФОРМІ.
2.1 Алгоритм симплекс-методу
Алгоритм симплекс-методу формулюється для Завдання лінійного програмування таким чином:
Крок 1. Формулювання Завдання лінійного програмування в канонічній ФОРМІ на Основі методу штучного базису, так щоб в матріці обмежень існувала одінічна базисних матриця. Для цього звітність, доповніті матрицю обмежень одінічнімі стовпцямі, Які повінні в сукупності з початково стовпцямі матріці обмежень Забезпечувати Існування одінічної базісної матріці. При цьом природнім чином мают буті введені відповідні штучні змінні, Які включаються в цільову функцію з великими позитивними Вагов коефіцієнтамі для Завдання на мінімум. У результаті запішемо початкова матрицю обмежень. в симплекс-таблицю, а КОЕФІЦІЄНТИ цільової Функції запішемо в рядок цієї табліці. У таблицю (*) такоже включімо компоненти початкових базисного решение, візначуваного вектором
Таблиця (*)
# № Базісні стовпціBsБазісне решение XsC1C2CmCm +1 CkCnA1A2AmAm +1 AkAn1A1 100 2A2 010 lAl 000 mAm 001 ОЦІНКИ
Крок 2. вичислення характеристичностью різніць (оцінок) за формулами и запис оцінок в-й рядок симплекс-табліці.
Крок 3. Обчислення ОЦІНКИ, что задовольняє умові,:
Если усе, то відповідно до Виконання крітерію оптімальності вектор - оптімальне решение, и далі слід перейти до Кроку 9, інакше - до Кроку 4.
Крок 4. Обчислення нового базисного решение з умови:
Крок 5. Обчислення компоненту нового базисного решение за формулами:
Крок 6. Обчислення ЕЛЕМЕНТІВ Нової симплекс-таблиці для-ої ітерації методу по формулах:
Крок 7. Коригування симплекс-таблиці з урахуванням змін Коефіцієнтів цільової Функції, відповідніх новому базисному рішенню. Формуємо таблицю (**).
Таблиця (**)
# # № Базісні стовпці базисних решение Xs_C1C2Cmm +1 CkCnA1A2AmAm +1 AkAn1A1 100 2A2 010 lAl 000 mAm 001 ОЦІНКИ
Крок 8. Перехід до Кроку 2.
Крок 9. Зупинка, реєстрація оптимального решение.
Таким чином, сформульованій алгоритм візначає кінцеву послідовність кроків, необхідніх для обчислення оптимального решение.
2.2 Рішення задачі оптімізації помощью засобой «Пошук решение» в Microsoft Excel
потужном засобой АНАЛІЗУ Даних MS Excel є надбудова Solver (Пошук решение). З ее помощью можна візначіті, при якіх значеннях Вказаною впливаючих осередків формула в цільовому осередку набуває потрібного значення (мінімальне, максимальне або рівне якій-небудь велічіні). Для процедури поиска реше...
