Коротка характеристика методів рішення З.Ц.П

Якщо при розв’язанні З.Ц.П. використовувати методику округлення оптимального плану у відповідній З.Л.П., то ми можемо одержати план або незадовольняючу систему обмежень (5.2), або, що птрапляє усередину області обмежень.

Висновок: прямо використовувати симплексний метод при розв’язанні З.Ц.П. не можна.

Є три способи розв’язання З.Ц.П.:

1) методи відсікання;

2) комбінаторні методи;

3) наближені методи.

Сутність методу відсікання: спочатку З.Ц.П. зважується симплексом-методом без урахування умов цілочисловості. Якщо оптимальний план відповідної З.Л.П. цілочисловий, то задача розв’язана; у протилежному випадку до обмежень З.Ц.П. додається нове обмеження, що володіє наступними властивостями:

1) воно повинне бути лінійним;

2) воно повинне відтинати знайдений оптимальний нецілочисловий план З.Л.П.;

3) воно не повиннео відтинати жодного цілочисловий плану.

Додаткове обмеження, що володіє зазначеними раніше трьома властивостями, називається правильним відсіканням.

Потім задача зважується з урахуванням нового обмеження, що вноситься додатковим рядком в останню симплекс-таблицю з оптимальним планом З.Л.П. У випадку потреби додаємо ще одне обмеження і розв’язуємо З.Л.П. симплексом-методом доти, поки не одержимо цілочислове розв’язання.

Таким методом,заснованому на правильному відсіканні,є метод Гомори.