Цілочисленне програмування - стор

Глава 7. ЦІЛОЧИСНЕ ПРОГРАМУВАННЯ

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

Характерні джерела цілісності (дискретності):

неподільність об'єктів, що подаються змінними (наприклад,x- число робочих або вагонів, що відправляються);

варіантність типу "так-ні" (наприклад, включати чи ні даний пакет у портфель цінних паперів);

заданість можливих значень нормативними документами (наприклад, перерізи дротів, діаметрів труб, розмірів профілів тощо);

комбінаторність (наприклад, розміщення об'єктів, порядок обходу об'єктів, впорядкування);

логічні умови (наприклад, фіксовані витрати мають місце лише за виробництва продукції).

Розрізняють завдання повністю цілочисленні/дискретні та частково цілочислові (змішані). В останніх вимога цілісності накладається не на всі змінні.

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

У цьому розділі розглядаються лише лінійні цілі завдання.

7.1. Проблема цілісності

На перший погляд може здатися, що ціле завдання вирішується простіше безперервним. При малій розмірності та вузьких діапазонах змінних завдання можна вирішити простим перебором. В інших випадках потрібні відповідні методи.

Незважаючи на лінійність моделі припустиме безліч цілісної задачі не є опуклим. Так, у цілковитій задачі воно являє собою безліч окремих точок, що мають цілочисельні координати. Методи лінійного програмування базуються на

опуклості допустимої множини і тому безпосередньо не можуть бути застосовні до цілих завдань.

Можна, звичайно, знехтувати вимогою цілісності і використовувати один із методів ЛП, але тоді, за рідкісним винятком, результат не буде цілим. Округлення дробових значень змінних є проблематичним. Дійсно, оскільки оптимальне рішення безперервної задачі лежить у вершині допустимої множини, округлення може призвести до неприпустимості. При двох дробових змінних є 4, а приnзмінних–2nваріантів округлення! Які з них дають допустимі рішення, можна визначити лише після перевірки всіх обмежень. При цьому слід мати на увазі, що, по-перше, ціла задача може виявитися нерозв'язною незважаючи на розв'язність безперервної задачі; по-друге, допустимість округленого рішення ще означає його оптимальність. Проілюструємо останню тезу відомим завданням про садівника.

За розрахунками садівника потрібно внести у ґрунт комплексні добрива у кількості 107 кг. Добрива продаються тільки в розфасованому вигляді: 1) мішок вагою 35 кг коштує 140 руб.; 2) мішок вагою 24 кг коштує 120 руб. Необхідно визначити варіант закупівлі добрив із мінімальними витратами.

Запишемо модель завдання:

Якщо знехтувати цілою чисельністю, то легко побачити, що оптимальним буде рішення

x1=3,x2=0.

Якщо заокруглити його за правилами арифметики, то отримаємо неприпустиме рішення.Округлення у велику сторону (x1=4,x2=0 ) призводить до допустимості, але чи є таке рішення оптимальним?

Щоб відповісти на це питання, розглянемо всі можливі

---