Page 35 - 6449

випадку алгоритм Гоморі стабілізується – тобто, стає неможливим додати
до системи обмежень задачі нове, відмінне від вже добавлених,
обмеження.
Наведемо приклад побудови додаткового обмеження за методом
Гоморі. Нехай при розв’язуванні деякої задачі лінійного програмування
оптимальний розв’язок був знайдений, і цьому розв’язку і цьому розв’язку
відповідає система обмежень такого вигляду:

  x  3.2 x  4.7 x  3.8 x  11 3 .
1 5 6 7

 x 2  5.0 x 5  4.2 x 6  5.3 x 7  12 6 .
 (1.41)
 x 3 2 . 0 x 5  2.8 x 6  4.7 x 7  13 9 .
 x  9.1 10 x 11 x  25 3 .
3 .
4 .
 4 6 7
Знаходимо рівняння з найбільшою дробовою частиною в правій
частині. В даному випадку це рівняння №3. Всі базисні змінні приймають
дробові значення, тоді як всі вони повинні бути цілочисельними.
Знаходимо в системі обмежень (1.41) рівняння з x 2 . 0 x  2 . 8 x  4 . 7 x  13 9 . .
3 5 6 7
Застосовуємо до нього нерівність Гоморі (1.38) в результаті
одержуємо:
2 . 0 x  2 . 0 x  4 . 0 x  9 . 0 (1.42)
5 6 7
Нерівність (1.42) добавляється до системи (1.41) як додаткове
обмеження, після чого ЗЛП розв’язуються симплекс-методом, але вже з
новою системою обмежень (1.41) - (1.42). В разі необхідності процедура
повторюється. Більше інформації про методи цілочисельного
програмування можна дізнатись відповідних літературних джерел, які
можна назвати класичними стосовно теорії лінійного програмування
[6,7,10,17].

1.7 Транспортна задача. Методи знаходження початкових
опорних планів
Серед задач лінійного програмування існує клас задач, для яких
через специфічну структуру матриці витрат розроблені спеціальні методи
їх розв’язування оскільки використання традиційного симплекс-методу
призводить до необхідності реалізації необґрунтовано великих об’ємів
розрахунків. Серед задач такого роду найбільш відомою та поширеною на
практиці є транспортна задача.
Транспортна задача формулюється таким чином: нехай на деяких n
пунктах виробництва або зберігання однотипної продукції знаходяться її

запаси b , i  1,.., n , а на деяких m пунктах споживання даної продукції
i
наявні потреби по кожному пункту складають a , j  ,m крім того
1
j
відомою є величина витрат на перевезення одиниці продукції з і-го пункту
виробництва або зберігаються на j-ий пункт споживання C .
ij
За таких умов необхідно розробити такий план перевезень, який
мінімізував би транспортні витрати.

35