Аналіз методів рішення задачі лінійного програмування симплекс методом
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
µревезень
4. Перевіряють умову для базисних клітин (їх повинно бути m+n-1): якщо ця умова не виконується, то в одну з вільних клітинок (як правило, в клітинку з найменшим тарифом) вписуюють число 0, і така клітина вважається базисною. Однак число 0 записуюють тільки в ті вільні клітинки, які не утворюють циклів з раніше зайнятими клітинками.
5. Обчислюють потенціали ui i vj. Кожному постачальнику (кожній стрічці) ставлять у відповідність деяке число ui, яке називають потенціалом постачальника Аі (і=1,m), і записуюють праворуч таблиці, а кожному споживачу (або стовпчику) деяке число vj , яке називають потенціалом споживача Вj (j=1,n), і записують під таблицею. Числа ui i vj вибирають так, щоб у будь-якій базисній клітинці їх сума дорівнювала тарифу, тобто ui+vj=сіj. Так, як кількість всіх потенціалів ui i vj складає m+n, а зайнятих клітинок m+n-1, то для визначення чисел ui i vj доведется вирішувати систему із m+n-1 рівнянь з m+n невідомими. Тому одному із невідомих потенціалів надають довільне значення. Тоді інші визначаються однозначно.
6. Для перевірки оптимальності плану переглядають вільні клітинки, для яких визначають оцінки ?іj різниця між тарифом клітинки і сумою потенціалів строки і стовпчика, тобто ?іj= сіj-( ui+vj). Економічно, оцінка покаже на скільки грошових одиниць змінятся транспортні витрати від завантаження даної клітинки одиницею вантажу. Якщо всі оцінки невід?ємні, тобто ?іj?0, то план оптимальний і залишається підрахувати транспортні витрати. Інакше переходять до пункту 7.
7. З від?ємних оцінок ?іj?0 вибирають мінімальну. Нехай це буде ?іk. Тоді клітинку (1, k) вводять в число базисних, тобто будують цикл по завантаженим клітинкам з початком в цій клітинці і перерозподіляють поставки так, щоб баланс циклу зберігався. Для цьогго вершинам циклу приписують знаки „+” і ”-”, які чергуються, (вільній клітинці (1, k) приписують позитивний знак „+”). В „мінусових” клітинках віднаходять найменший вантаж w, тобто w=min xіj=xst, який і переміщається клітинками замкнутого циклу, тобто додається до перевозок xіj в клітинках зі знаком „+” (включаючи вільну) і віднімається з перевозок xіj в клітинках із знаком ”-”. З цього слідує, що клітинка (s, t) стане вільною і змінна xst вийде з базису. Значення інших базисних змінних переписуюються. Таким чином, отримуюють або одержують нову транспортну таблицю с поліпшеним планом, для якого транспортні витрати змінюються на величину ?1k* xst. Переходять до пункту №4.
3.2 Симплекс-метод
Симплекс-метод цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.
Симплекс-метод метод розвязання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розвязку; симплекс-метод також називають методом поступового покращення плану.
Розглянемо опис методу:
Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:
(3.2.1)
(3.2.2)
де X = (x1, …, xn) вектор змінних, C = (c1, …., cn), B = (b1, …, bm)T, Aj = (a1j, …, amj)T, j = 1, …, n задані вектори, T знак транспонування, та відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану Тоді
(3.2.3)
(3.2.4)
де значення лінійної форми на даному плані. Так як вектор-стовпці матриці A лінійно незалежні, будь який із векторів умов Aj розкладається по ним єдиним чином:
(3.2.5)
(3.2.6)
(3.2.7)
де xij - коефіцієнт розкладання. Система умов
(3.2.8)
zk ? 0, xj = 0, j = m + 1, …, n, j ? k (3.2.9)
при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної xk при русі по цьому проміню дорівнює ?, тоді значення базисних змінних дорівнюють xi(?). В цих позначеннях рівняння (5) можна представити в вигляді:
(3.2.10)
помноживши рівняння (3) на ? при j = k та віднявши від рівняння (1), отримаємо:
(3.2.11)
Із рівнянь (10-11) отримаємо:
(3.2.12)
Оскільки xi(?) при ? = 0 визначають план задачі, то найбільше ?, яке не порушує обмеження xi (?) ? 0, визначається із умови:
(3.2.13)
де I = {i | xik > 0}
В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та ? > 0. Значення лінійної форми при ? = ?0 визначається із рівнянь (9), (4), (2)
(3.2.14)
де ?k = zk ck. Очевидно, ?j = 0 для j = 1, …, m.
Нехай початковий базис із m одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розвязання задачі лінійного програмування складається із наступних операцій:
1. Знайти ?k = minj?j. Якщо ?k = 0, тоді план, який розглядається оптимізовано; якщо ?k < 0, вектор Ak вводиться в базис;
2. Знайти ?0 та l для якого , із формули (10). Якщо I = ? порожня множина, лінійна форма необмежена зверху; якщо I ? ? вектор Al виводиться із базису;
3. По знайденим l, k обчислити нові значення елементів таблиці по формулам
Перетворення (12) замінює вектор коефіцієнтів Xk = (x1k, …, xmk) на одиничний вектор Xk з xlk = 1. В силу монотонного збільшення x0 повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму. Початковий опорний план з одиничним базисом можна отримати, розвязавши описаним алгоритмом допоміжну задачу,
(3.2.1