Оптимальний план оптимальний план

Задача про рюкзак

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

Є рюкзак місткістю V і n предметів об’ємами v₁, v₂,...,v_n і вартостями с₁, c₂ ,..., c _n. Потрібно впакувати рюкзак так, щоб вартість упакованих предметів була максимальною.

Складемо математичну модель цієї задачі.

Нехай x_j – змінна, що приймає тільки два значення: 0 або 1, причому x_j =0, якщо j- й предмет не впаковується в рюкзак; x_j = 1, якщо j- й предмет упаковується в рюкзак. Тоді задача записується так:

при обмеженнях

Ця ЗЦЛП називається задачею булєва програмування. Обмеження задачі можна записати інакше:

7.4. Вирішення ЗЦП методом округлення

Метод округлення - найпростіший метод наближеного вирішення ЗЦЛП. Його сутність полягає в тому, що вирішується ослаблена задача (як задача лінійного програмування) і отримане оптимальне рішення ЗЛП округляється до цілочислового рішення. Цей метод має два суттєвих недоліки:

1) у результаті округлення може вийти неприпустиме рішення;

2) рішення, отримане в результаті округлення, будучи припустимим, може значно відрізнятися від оптимального.

Приклад 1.

Вирішивши геометрично ослаблену задачу, одержуємо оптимальне рішення:

Зробимо округлення:

1) x₁=2; x₂=0. Одержимо неприпустиме рішення - не задовольняється обмеження 7x₁+4x₂<=13 (дійсно, 7*2+4*0<=13 – хибна нерівність).

2)х₁=1; х₂=0. Це припустиме рішення. Значення цільової функції f=21*1+11*0=21, що значно відрізняється від оптимального значення.

Оптимальне рішення цієї ЗЦЛП таке: х₁=0; х₂=3; f_max =33.

Метод округлення можна використовувати тоді, коли цільова функція малочутлива до змін змінних у межах одиниці.

7.5. Метод гілок і меж

Цей метод точного вирішення ЗЦЛП найчастіше використовується на практиці. Він полягає в наступному.

Спочатку вирішується ослаблена задача. Якщо отримане оптимальне рішення цілочислове, то ЗЦЛП вирішена. Якщо ж оптимальне рішення ЗЛП не є цілочисловим, то робимо "розгалуження" у такий спосіб. Нехай змінна х_s прийняла в оптимальному рішенні значення q_s, що не є цілим. Тоді розглядаємо дві ЗЦЛП. Перша виходить додаванням обмеження х_s <=[q_s], друга – додаванням обмеження х_s >=[q_s] + 1, де [q_s] - ціла частина числа q_s.

Кожна із цих двох задач аналогічним способом може розбитися ще на дві задачі і т.д.

Якщо в результаті вирішення якої-небудь із задач виходить цілочисловий оптимальний план, то значення А цільової функції при цьому плані відіграє роль "межі": якщо в результаті вирішення чергової ЗЛП з'ясується, що оптимальне значення цільової функції "гірше" А, тоді така задача "не гілкується".

Недолік методу гілок і меж полягає в тому, що часто оптимальне рішення ЗЦЛП досягається після дуже великої кількості розгалужень, але при наявності Excel цей недолік усунений.

Повернемося до ЗЦЛП прикладу 1.

Використовуємо Excel для відшукання оптимальних планів ослаблених задач.

Вихідна ЗЦЛП №1

(оптимальний план )

оптимальний план ОПР порожня.

х₁=1, х₂=1, f_max=32 х₁=, х₂=2, f_max=37

A=32- межа

оптимальний план ОПР порожній

х₁=0, х₂=, f_max=35,75

Оптимальний план ОПР порожній

х₁=0, х₂=3, f_max=33>A

Оптимальний план ЗЦЛП: х₁=0, х₂=3, f_max=33.

7.6. Геометричний метод рішення ЗЦП

У випадку, коли число змінних у ЗЦП дорівнює двом, завдання можна вирішити геометрично.

Алгоритм вирішення ЗЦП геометричним методом такий самий як і для рішення ЗЛП (див. п. 5), але на відміну від останнього в отриманій ОПР до розгляду беруть тільки ті точки, координати яких є цілі числа, і пошук оптимуму цільової функції здійснюється саме на отриманій множині точок з цілими координатами.

ЛІТЕРАТУРА

1. Глушик І., Пенцак Л. Математичне програмування. - Львів, Новий Світ-2006.

2. Кучма М. Математичне програмування: приклади і задачі. - Львів, Новий Світ-2006.

3. Дякон А., Ковальов М. Математичне програмування, - Київ, Вид-во Європ. Ун-ту, 2006.

4. Мазаракі Л., Толбанов К. Математичне програмування в Excel. - Київ, Четверта хвиля, 1998.

5. Таха X. Введення в дослідження операцій. (В 2-х книгах).-
М.:Мир,1985

6. Міну М. Математичне програмування. Теорія й
алгоритми.-М.: Наука, 1990.

ЗМІСТ

1. РІШЕННЯ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ МЕТОДОМ ГАУСА - ЖОРДАНА.......................................................................... 4

1.1. Основні поняття..................................................... 4

1.2. Приведення системи лінійних рівнянь до жорданової форми..... 3

1.3. Поняття загального, часного й базисного рішень............... 5

2. РІШЕННЯ СИСТЕМ ЛІНІЙНИХ НЕРІВНОСТЕЙ.............6

3. РІШЕННЯ ЛІНІЙНИХ РІВНЯНЬ В EXCEL...................8

4. ЗАГАЛЬНІ ВЛАСТИВОСТІ ЗАДАЧ ЛІНІЙНОГО

ПРОГРАМУВАННЯ...........................................10

4.І. Приклад задач лінійного програмування – задача про використання обладнання.................................................... 10.

4.2. Задача про використання сировини......................... 12

4.3. Задача складання раціону (задача про дієту)..................12

4.4. Загальна постановка задач лінійного програмування (ЗЛП).....13

5. ГЕОМЕТРИЧНИЙ МЕТОД ВИРІШЕННЯ ЗЛП............. 14.

6. ТАБЛИЧНИЙ ПРОЦЕСОР EXCEL У ВИРІШЕННІ ЗЛП.....18

7. ЦІЛОЧИСЛОВЕ ЛІНІЙНЕ ПРОГРАМУВАННЯ............23

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

7.2. Цілочислова задача про використання сировини.................24

7.3. Задача про рюкзак..........................................24

7.4. Вирішення ЗЦП методом округлення..........................25

7.5. Метод гілок і меж...........................................26

7.6. Геометричний метод рішення ЗЦП............................ 28

Література......................................................29

Зміст............................................................ 29

Дата добавления: 2014-01-07