Page 170 - 5637

додаткове обмеження. Для цього беремо -й рядок з дробовим членом і записуємо

додаткове обмеження

= − + +. . . + > 0,

де = − [ ] ( = 1, … , ); [ ] – символ цілої частини числа . Півпростір

{ ≥ 0} може містити кожну цілу точку допустимого багатогранника і не містити

раніше знайденої оптимальної точки. Додавши (у вигляді рядка) нове обмеження,
заповнимо нову таблицю умов. Описаний процес повторюється до тих пір, поки за
кінцеве число кроків або знаходиться оптимальне цілочисельне рішення, або ж

виявляється, що такого рішення у задачі (8.7), (8.8) немає.

ПРОГРАМА GOMORY

Призначення: рішення задачі цілочисельного лінійного програмування.

Призначена для визначення ( − 1)-мірного цілочисельного вектора

[ (1), … , ( − 1)] , мінімізує цільову функцію = (1, 1) (1)+. . . + (1, − 1) ∗

∗ ( − 1), за умови (1) ≥ 0, … , ( − 1) ≥ 0, ( , 1) (1)+. . . + ( , − 1) ≤

≤ ( , ). Написана на мові ПЛ/1, прототипом програми послужила Алгол-процедура

GOMORY [62].

Параметри:

— розмірність, на одиницю більша розмірності оптимізується вектора параметрів;

— число рядків матриці (симплекс-таблиці);

— матриця (симплекс-таблиця) розміру ∗ з атрибутами ;

— оптимальне значення цільової функції;

— індикатор, що дозволяє судити про успішність виконання завдання:

= 0 при успішному виконанні пошуку оптимуму, = 1 в іншому
випадку.

Мінлива описується за атрибутами , a – з атрибутами

(1), атрибути параметрів і задаються за умовчанням. Перші

ненульові елементи стовпців матриці повинні бути позитивними, частину вхідних

значень задається при постановці завдання, інші присвоюються самою програмою

.

Звернення: ( , , , , , );