Задача математичного програмування Тема 1 Питання термінології, історіографія назв
жүктеу/скачать 3.01 Mb.
|
- Бұл бет үшін навигация:
- Целочисленное програмування
- ЛП задачі
| Транспортна задача.
Ф. Л. Хітчкок у 1941 рік уперше поставив транспортну задачу. Нехай є m виробників, у кожного з яких знаходиться ai (i = 1, m) одиниць однорідного товару. Цей товар потрібно доставити n споживачам, потреба в товарі яких відповідно дорівнює b j , ( j= 1, n) одиниць, таким чином, щоб загальна величина транспортних витрат була мінімальною. Причому: Відомі такі параметри: cij , (i=1,m; j= 1,n) - вартість перевезення од. товару від i-го виробника j-му споживачеві. xij , (i= 1,m; j= 1,n)– - кількість товару, що перевозиться від i-го виробника j-му споживачу. Математична модель транспортної задачі прийме вигляд: Де (1.5) - цільова функція завдання , - описує транспортні витрати; і Вимоги задач (1.6) - весь продукт з пунктів виробництва повинен бути вивезений; (1.7) - попит споживачів повинен бути задоволений; (1.8) - умови невід'ємності змінних виключають зворотні перевезення. Ну а за умовами завдання а й b мають такі значення що Ці завдання, що ми продивилися є прикладами завдань лінійного програмування Ми починаємо розуміти, який корисний і широкий за сферою застосування математичний апарат ми вивчаємо. Тема 14 Целочисельне програмування Целочисленное програмування - це розділ математичного програмування, в якому на всі або деякі змінні додатково накладається обмеження целочисленности. Як правило, тут маємо на увазі клас задач - задачі лінійного цілочисельного програмування. Від розуміння суті класу даних задач слідує і найпростіший підхід до їх вирішення: метод вирішення ЦЛП завдання шляхом округлення рішення ЛП завдання (з деякими нюансами). Таким чином, зводимо ЦЛП до звичайної ЛП задачі з перевіркою результату на цілочисельність цілочисельних змінних (ЦЗ). Якщо рішення нецелочисельне для ЦЗ, то округленням рішення до найближчого цілого в допустиму область отримаємо можливе рішення. Якщо ж можливі кілька варіантів округлення (цілочисельний вектор), краще рішення знаходимо перебором. Такий похід допустимий для випадків, коли область оптимального рішення ЦЗ містить порівняно великі цілочисельні значення: наприклад 1000 упаковок медикаментів або 400 фахівців або 200 пускових ракет і т.д.- тобто, коли похибка округлення буде давати десяті і соті відсотка зміни функціоналу ЛП завдання. Тоді механізм округлення ЦП не істотно впливатиме на значення функціоналу ЛП завдання і, тобто, не позначиться на оптимальному рішенні ЦЛП. Маємо тут на увазі, що в допустимій області, оптимальне значення функціоналу ЦЛП задачі не може перевищувати оптимальне значення функціоналу відповідної ЛП задачі (відповідної ЛП задачі, де зняті обмеження на цілочисельність). !!! Тому-що ЦЛП рішення забов’язано бути у середині ДО ЛП задачі Але, якщо значення ЦП невеликі - кількість ракет 10-20 або взагалі у нас присутні в задачі булеві змінні (0-1), то такий підхід не дасть оптимального рішення ЦЛП завдання і слід застосовувати спеціальні методи цілочисельного програмування (ЦП). жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|