Навигация
1.4 Двоїстий симплекс-метод
Двоїстий симплекс-метод і симплекс-метод за алгоритмом досить схожі. Однак двоїстий симплекс-метод можна застосовувати при рішенні задач лінійного програмування, вільні члени системи рівнянь якої можуть бути будь-якими числами (при рішенні задачі симплексним методом ці числа передбачалися ненегативними).
Нехай за умовою задачі потрібно визначити максимальне значення функції:
.(1.4.1)
Нехай
(1.4.2)
де 
- одиничні вектори.
Для того, щоб вирішити задачу двоїстим симплекс-методом потрібно виконати дві умови. Спочатку необхідно знайти так званий псевдо план задачі. Рішення системи лінійних рівнянь(1.4.2), приймаючи до уваги базис(одиничні вектори), називається псевдопланом задачі, якщо всі умови даної системи задоволені. Потім рішення зводиться до перевірки отриманого псевдоплану. Якщо він оптимальний, то отримане значення і є розв’язком задачі. Якщо ж ні, то потрібно знову встановлювати псевдоплан. Після цього, вибирають рядок, що дозволяє, за допомогою визначення найбільшого по абсолютній величині негативного числа стовпця вектора 
і результуючого стовпчика, знаходження найменшого по абсолютній величині відношення елементів (
) і рядка до відповідного негативним елементам результуючого рядка. Знаходять новий псевдоплан і цикл розв’язку задачі повторюється.
В порівнянні з методами, описаними раніше, двоїстий симплекс-метод дає змогу вирішувати задачі лінійного програмування, системи обмежень яких при позитивному базисі містять вільні члени будь-якого знаку. Цей метод дозволяє зменшити кількість перетворень системи обмежень, а також розміри симплексної таблиці.
1.5 Транспортна задача
В найпростішому варіанті транспортна задача формулюється наступним чином: є n постачальників із запасами однорідного штучного товару 
та m споживачів із потребами цього товару 
. Не порушуючи загальності, можна вважати транспортну задачу закритою, тобто, що сума всіх запасів дорівнює сумі всіх потреб, в противному разі задача є відкритою і простими відомими методами (введенням фіктивного постачальника чи фіктивного споживача) зводиться до закритої. Нехай матриця 
є матрицею цін перевезень, тобто кожен її елемент 
є ціною за перевезення одиниці продукції від i–го постачальника j–му споживачу, а матриця 
такої ж розмірності є планом перевезень, тобто кожне 
є цілим невід’ємним числом, що дорівнює кількості товару, що перевозиться від i–го постачальника j–му споживачу. Метою розв’язку транспортної задачі є пошук такого плану перевезень Х, при якому загальна вартість перевезень була б найменшою з можливих за умови, що весь товар від постачальників перевозиться до споживачів. Транспортна задача є задачею цілочислового лінійного програмування. З основами лінійного програмування можна ознайомитись, з науковим обґрунтуванням алгоритмів розв’язку задач лінійного програмування, зокрема транспортної задачі. Відзначимо лише, що по-перше, жоден з відомих алгоритмів не є досконалим, а по-друге, зажди пропонується шукати один оптимальний план перевезень, а решта оптимальних планів залишається або без уваги, або в кращому випадку залишається на розгляд методами після оптимізаційного аналізу. Досі було важко запропонувати достойну альтернативу цим методам через відсутність потужної обчислювальної техніки, але тепер це можливо[4].
Для сучасної ЕОМ не представляє ніяких складностей вирішення задач за допомогою даного методу, що можна сміливо віднести до першої переваги методу розв’язку транспортної задачі. Навіть враховуючи те, що кількість варіантів дуже швидко ростиме зі збільшенням кількостей постачальників, споживачів, запасів та потреб, в багатьох випадках ЕОМ розв’яже задачу цим методом швидше, ніж людина – іншим методом. Зазначимо, що описаний алгоритм підрахунку кількості можливих варіантів є водночас і алгоритмом власне перебору цих варіантів.
Другою перевагою цього методу є те, що в ході перебору легко отримати не один, а всі оптимальні плани перевезень , для яких досягається спільне мінімальне значення вартості перевезень, які в свою чергу, для зручності аналізу можна згрупувати по кількості відмінних елементів.
Третьою суттєвою перевагою цього методу є його прозорість (порівняно з іншими методами) та можливість легкого програмування. Єдиним недоліком цього методу є те, що при великих розмірах матриці та великих значеннях обсягів потреб та запасів час роботи програми може складати кілька годин, хоча і такий час може бути виправданий, коли мова йде про конкретну практичну задачу.
Похожие работы
... зумовлюється метою, якої хочуть досягти даною геометричною інтерпретацією та особливостями структури самої задачі, в тому числі й формою її представлення. Для геометричної інтерпретації візьмемо основну задачу лінійного програмування у другій стандартній формі. Для наочності розглянемо найпростіший випадок, коли в системі обмежень (26) і цільовій функції (25) є лише дві змінних, Розглянемо розв' ...
... і (усі сj’ ≥0), але не задовільняє критерії допуску (не всі ві ≥0). Варіант симплекс метода, який приміняється для рішення таких задач, називається двоїстим симплекс методом. За його допомоги рішаються задачі лінійного програмування виду: (4.3.1) де система обмежень має такий вигляд і всі приведені коефіцієнти цільової функції сj’ ≥0, і=1,n. При цьому умова ві ≥0, ...
... 20 0 Mf 0 0 0 1 0 0 0 0 Отже, х* = (12, 8, 60), L(x*)max = 20. Задача 3 Для задачі побудувати двоїсту, розв’язати і за розв’язком знайти розв’язок двоїстої: Розв’язання: Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею. Економічну інтерпретацію кожної з пари задач розглянемо на прикладі виробничої задачі. Початкова задача: max z ...
... розвиток як математична теорія лінійного і нелінійного програмування, так і додаток її методів до дослідження різних економічних проблем. У 1949 р. американським математиком Дж. Данцигом (GB Dantzig) був опублікований симплекс-метод - основний метод рішення задач лінійного програмування. Термін «лінійне програмування» вперше з'явився в 1951 р. в роботах Дж. Данцига і Т. Купманса. При всьому ...
0 комментариев