д зведемо задачу на максимум до задачі на мінімум. Для цього в кожному стовпці матриці З знайдемо максимальний елемент і віднімемо з нього елемент відповідного стовпця. Отримаємо матрицю Сj задачі про призначення:
В
яку будемо вирішувати на мінімум:
В
Для отримання наближеного рішення скористаємося способом Фогеля для знаходження початкового опорного плану транспортної задачі. У кожному ряду матриці Сi знайдемо мінімальний і найближчий до нього елементи і їх різниця по абсолютній величині записуємо в кінці відповідного ряду праворуч і знизу (табл.3.1). Знаходимо максимальну з цих різниць (число 5 укладено в рамку). В ряду, відповідному максимальної різниці, знаходимо мінімальний елемент . Подумки викреслюємо з матриці (табл. 3.1) рядок і стовпець, відповідні цьому елементу. Фіксуємо отримане призначення. Для нашого прикладу закріплюємо третє транспортне засіб за третім маршрутом, це закріплення в табл. 3.1 підкреслено. З залишилася матрицею чинимо аналогічно попередньому. Всі обчислення зведені в табл.3.1.
Таблиця 3.1
В
План призначення (1-4), (2-1), (3-3), (4-2),
maxZ = с14 + с21 + С33 + С42 = 12 + 7 + 15 +14 = 48.
. Метод відсікання
Алгоритм методу Гоморі для вирішення повністю целочисленной завдання лінійного програмування. Розглянемо повністю цілочисельну задачу лінійного програмування
(4.1)
(4.2)
(4.3)
(4.4)
Алгоритм Гамори складається з декількох етапів:
1. Вирішується задача (4.1) - (4.3) з відкинутим умовою цілочисельності. p align="justify"> 2. Отримане оптимальне рішення (якщо воно існує) перевіряється на цілочисельність. Якщо умова цілочисельності виконується по всім змінним, то оптимальне рішення задачі (4.1) - (4.4) збігається з оптимальним рішенням задачі (4.1) - (4.3). Якщо це рішення не виконується хоча б по одній змінній, то переходять до третього етапу. Якщо завдання (4.1) - (4.3) виявляється нерозв'язною, то завдання (4.1) - (4.4) теж не має рішення. p align="justify"> 3. Будується додаткове обмеження, відтинає частина області, в якій міститься оптимальне рішення задачі (4.1) - (4.3) і не міститься жодного допустимого рішення задачі (4.1) - (4.4). p align="justify">. Останній етап передбачає повернення до ЗЛП з відкинутим умовою цілочисельності, але з розширеною системою обмежень, в яку включено додаткове обмеження, отримане на третьому кроці. До розширеної системі обмежень знову застосовується симплексна процедура. Якщо знайдене таким чином рішення буде знову нецілим, то фор...
