Економічні задачі лінійного програмування і методи їх вирішення
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
nbsp;
відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану . Тоді
, (1)
, (2)
де значення лінійної форми на даному плані. Так як вектор-стовпці матриці A лінійно незалежні, будь який із векторів умов Aj розкладається по них єдиним чином:
, (3)
, (4)
де xij коефіцієнт розкладання. Система умов
, (5)
zk ? 0, xj = 0, j = m + 1, …, n, j ? k (6)
при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної xk при русі по цьому променю дорівнює ?, тоді значення базисних змінних дорівнюють xi(?). В цих позначеннях рівняння (5) можна представити в виді
. (7)
помноживши рівняння (3) на ? при j = k та віднявши від рівняння (1), отримаємо
.(8)
Із рівнянь (7-8) отримаємо
. (9)
Оскільки xi(?) при ? = 0 визначають план задачі, то найбільше ?, яке не порушує обмеження xi (?) ? 0, визначається із умови
. (10)
де I = {i | xik > 0}.
В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та ? > 0. Значення лінійної форми при ? = ?0 визначається із рівнянь (9), (4), (2)
,
де ?k = zk ck. Очевидно, ?j = 0 для j = 1, …, m.
Нехай початковий базис із m одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розвязання задачі лінійного програмування складається із наступних операцій:
- знайти ?k = minj?j. Якщо ?k = 0, тоді план, який розглядається оптимізовано; якщо ?k < 0, вектор Ak вводиться в базис;
- знайти ?0 та l, для якого
, із формули (10). Якщо I = ? порожня множина, лінійна форма необмежена зверху; якщо I ? ? вектор Al виводиться із базису;
- за знайденими l, k обчислити нові значення елементів таблиці за формулами
(12)
,
де та перейти до виконання операції (1) з новими значеннями всіх xij = xij.
Перетворення (12) замінює вектор коефіцієнтів Xk = (x1k, …, xmk) на одиничний вектор Xk з xlk = 1. В силу монотонного збільшення x0 повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму.
Початковий опорний план з одиничним базисом можна отримати, розвязавши описаним алгоритмом допоміжну задачу
,
при обмеженнях
;
,
яка містить одиничний базис, який складається із векторів An+1, …, An+m. Цим векторам відповідають штучні змінні із значеннями , i = 1, …, m. Якщо в оптимальному розвязку цієї задачі , вихідна задача не має розвязку. Якщо ж та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які за формулами (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення z0 може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин bi на bi + ?i, де ?i достатньо малі, при вдалому виборі ?i не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.
Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця A-1, обернена до базисної матриці.
3. Прикладний розділ
3.1 Вирішення задачі лінійного програмування симплекс-методом
Для розробки математичної моделі задачі позначимо:
x1 кількість продукту А;
x2 кількість продукту В;
Цільова функція буде мати вид:
Z=x1+2x2mах
Система обмежень:
3 x1+3 x2 =0, j=1..2
Зведення задачі до канонічного виду: Zmax = x1+2x2 при умовах:
3x1+3x2+x3 = 15 2x1+6x2+x4 = 18 4x1+x5 = 16 x1+2x2+x6 = 8 Xj>=0, j=1..6
Таблиця 5.
БазисСПлан120000X3015331000X4018260100X5016400010X608120001Zj-Cj 0-1-20000
Таблиця 6.
БазисСПлан120000X306201-0,500X22340238104033000X5016400010X6024023800-0,333301Zj-Cj 6-0,3333004023800
Таблиця 7.
БазисСПлан120000X1131040210-0,2500X22201-0,16674026900X50400-2110X60100-0,1667-0,2501Zj-Cj 700403304026900
Відповідь: Zmax =7, Xопт =(3 ; 2 ; 0 ; 0 ; 4 ; 1).
Це свідчить про те, що максимальний прибуток підприємства буде дорівнювати 7 грн., а виробництво продукції А і В складає відповідно 3 і 2 одиниці.
3.2 Вирішення задачі лінійного програмування за допомогою Пошуку рішень у середовищі Microsoft Office Excel 2003
Пошук рішень одна із сервісних можливостей пакету Microsoft Office Excel 2003. Він представляє собою спрощений варіант симплекс-методу.
Пошук рішень викликається за допомогою меню Сервіс, далі вибираємо підменю Надстройки і натискаємо Пошук рішень [12].
Методика знаходження рішення задачі за допомогою Пошуку рішень в Excel полягає в тому, що користувач задає основні параметри завдання (цільову функцію, систему обмежень) і змінні клітинки, яким дають деякі довільні початкові значення (одиниці). Після цього Пошук рішень автоматично перебирає всі можливі значення змінюваних клітинок так, щоб вони задовольняли обмеженням, а цільова функція приймала задані значення. Таким чином, порядок виконання Пошуку рішень такий [3]:
1. На аркуші Excel формується масив