Короткі теоретичні відомості. 1. Постановка задачі про призначення

Практичне заняття №7

Контрольні питання

Завдання до теми

1. Постановка задачі про призначення.

2. Отримання начального рішення задачі про призначення угорським методом шляхом занульовання матриці витрат С.

3. В випадку не оптимальності отриманого рішення перехід угорським методом до другого рішення.

4. Економічний аналіз отриманого оптимального рішення задачі про призначення.

1. Постановка задачі про призначення.

2. Математична модель задачі про призначення.

3. Задача про призначення як різновид Т З зі своєю специфікою.

4. Розв’зання (план) задачі про призначення.

5. Теорема 1 про мінімізацію функціонала.

6. Теорема 2 (Фробеніуса).

7. Застосування теорем 1 і 2 для занулення матриці С.

8. Визначення «незалежного» нуля в матриці С.

9. Зв'язок “незалежних” нулів з оптимальністю плану задачі про призначення.

10. Суть угорського метода при розв’язанні задачі про призначення.

11. Якщо при розв’язанні задачі про призначення угорським методом не отриманий оптимальний план, яким буде подальше розв’язання задачі?

Література: [1, с. 213 – 258; 2, с. 231 – 270; 10, с. 22 – 31; 12, с. 17 – 38].

Тема. Розв´язання задачі цілочислового програмування

Мета: навчитися розв´язуватизадачі цілочислового програмування методом Гоморі.

Загальний вигляд задачі цілочислового програмування (З Ц П):

; (19)

(20)

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

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

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

З Л П;

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

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

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

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

Дата добавления: 2015-05-23