я оптимальний план і, якщо він нецілочисельне, будується додаткове обмеження, відтинає знайдений оптимальний план, але не відтинає жодного цілочисельного плану.
Ця ідея, що належить Д. Данцигу і Р. Гомори, вперше була представлена ​​у формі додаткового обмеження:
(3.1)
(сума небазисних компонент оптимального плану повинна бути відмінна від нуля; хоча б одна з небазисних компонент має бути ненульовий). Справді, оптимальний план з нульовими значеннями небазисних компонент цій умові не задовольняє, що підтверджує відсікання цього плану від вихідної безлічі.
На жаль, для абсолютної більшості завдань швидкість збіжності процесу таких відсікань мала. Тому Р. Гомори запропонована інша форма додаткового обмеження. Так, якщо компонента плану, обумовлена ​​k-м рівнянням системи обмежень, нецілочисельне, то додається обмеження
, (3.2)
де f k - дрібна частина компоненти плану (правій частині обмеження) і f kj - дрібна частина коефіцієнта при X j (ціла частина числа - найбільше ціле, що не перевищує це число; дрібна частина числа дорівнює різниці між числом і його цілою частиною), S * - нова додаткова змінна.
Можна зменшити обсяг перетворень, якщо керуватися такими правилами:
1) вибирати в якості базового для побудови додаткового обмеження рівняння, що визначає компоненту плану з найбільшою дробовою частиною;
2) для введення в базис опорного плану розширеної задачі вибирати змінну, для якої досягається мінімум з відносин абсолютних значень D j до значень f kj ;
3) якщо одна з раніше введених додаткових змінних увійшла в базис, її і відповідне їй рівняння можна відкинути (ця ситуація пов'язана з появою більш жорсткого умови, що перекриває дію раніше введеного).
Поява додаткового обмеження і додаткової змінної знову приводить до проблеми вибору початкового опорного плану розширеної задачі і до використання з цією метою штучної змінної. Слід зауважити, що якщо при пошуку змінної, исключаемой з базису, значення Q (обумовлений з урахуванням додаткового обмеження) відповідає цьому обмеженню, то можна відмовитися від використання штучної змінної (вона все одно виведеться з базису на цьому ж кроці рішення).
Зауважимо, що для цілочисельних програм може виявитися відсутність цілочисельних планів (Суперечливість обмежень). p> Для запропонованого тут методу доведена кінцівку процесу відсікань, але число цих відсікань непередбачувано (цілком може виявитися швидке вирішення завдань з десятками змінних і обмежень і фантастично тривалий для задач невеликих розмірів).
В
4. МАТЕМАТИЧНА І ТЕХНІЧНА ПОСТАНОВКА ЗАВДАННЯ
Математичну і технічну постановку задачі можна сформулювати наступним чином. Розробити програмне забезпечення на вбудованій мові середовища MatLAB, що дозволяє вирішувати лінійні програми симплексним методом з ...
