Cуть та особливість cимплексний метод
Цілочислове лінійне програмування.
До задач цілочислового лінійного програмування належать задачі лінійного програмування, на змінні яких накладається умова, щоб вони були цілі. Наприклад, задачі визначення потужності підприємств, технологічних способів виробництва продукції, крім матеріалів, розподіл транспортних засобів за рейсами і т.п.
В загальному випадку цю задачу можна сформулювати так: знайти максимум функції
за умов
m
F = åc j x j j =1
/51/
n
å aij x j = bi ,
j =1
x j ³ 0,
(i = 1, m),
( j = 1, n),
/52/
/53/
x j - цілі ( j = 1, n).
/54/
Для розв’язку задач цілочислового програмування застосовують спеціальні методи. Останнім часом значного поширення набули два методи: Гоморі та метод розгалужень і меж.
Метод Гоморі.
Розв’язок задачі цілочислового програмування методом Гоморі починається з визначення симплексним методом оптимального плану задачі без урахування цілочисловості змінних. Після того, як план знайдено, розглядають його компоненти. Якщо всі змінні цілі, то одержаний план є оптимальним для задачі цілочислового програмування.
Якщо ж оптимальний план має змінні, значення яких подано у вигляді дробу, то, використовуючи нерівність
|
/55/
знаходимо розв’язок задачі /51/-/54/, /55/.
|
|
|
|
та b*
- перетворені початкові величини aij , bi , значення яких
|
|
|
цілочисловості/, а
f (aij ) та
f (bi ) - дробні частини чисел. Під дробовою частиною числа а
розуміється найбільше ціле число, яке не перебільшує а.
Метод розгалужень та меж
Цей метод засновано на послідовній побудові «дерева» вершин, кожна з яких відповідає оптимальному плану допоміжної задачі: мінімізувати /максимізувати/ цільову функцію за заданих умов з допоміжними обмеженнями
xk £ [xko ] , або
xk ³ [xko ] +1,
де [xko ]- ціла частина змінної. Для одержання вершин розраховують оцінки, рівні значенням цільових функцій відповідних задач лінійного програмування з урахуванням допоміжним обмежень.
2Метод найменшої вартості.
Спочатку по всій транспортній таблиці ведеться пошук клітини з найменшою вартістю. Потім змінній в цій клітині присвоюється найбільше значення, що допускається обмеженнями на попит і пропозицію. (Якщо таких змінних кілька, вибір довільний.) Далі викреслюється відповідний стовпець або рядок, і відповідним чином коректуються значення попиту і пропозицій. Якщо одночасно виконуються обмеження і щодо попиту, і щодо пропозиції, викреслюється або рядок, або стовпець (точно так само, як у методі північно-західного кута). Тоді проглядаються невикреслені клітини, і вибирається нова клітина з мінімальною вартістю. Описаний процес триває до тих пір, поки не залишиться лише один невикреслений рядок або стовпець.
|
|
|
Cуть та особливість cимплексний метод
Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості змінних необхідно застосовувати інший метод. З властивостей розв’язків задачі лінійного програмування відомо: оптимальний розв’язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв’язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (допустимих планів задачі, які ще називають опорними). Порівняння вершин багатогранника можна здійснювати тільки після відшукання якоїсь однієї з них, тобто знайшовши початковий опорний план. Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів 
. Отже, загальна кількість опорних планів визначається кількістю комбінацій 
. Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Тому необхідне використання методу, який уможливлював би скорочення кількості обчислень. 1949 року такий метод був запропонований американським вченим Дж. Данцігом — так званий симплексний метод, або симплекс-метод.
|
|
|
Ідея цього методу полягає в здійсненні спрямованого перебору допустимих планів у такий спосіб, що на кожному кроці здійснюється перехід від одного опорного плану до наступного, який за значенням цільової функції був би хоча б не гіршим за попередній. Значення функціонала при переході змінюється в потрібному напрямку: збільшується (для задачі на максимум) чи зменшується (для задачі на мінімум).
Процес розв’язання задачі симплекс-методом має ітераційний характер: однотипні обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує.
Отже, симплекс-метод — це ітераційна обчислювальна процедура, яка дає змогу, починаючи з певного опорного плану, за скінченну кількість кроків отримати оптимальний план задачі лінійного програмування.
|
|
|
Дата добавления: 2018-04-05; просмотров: 337; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!