ельного програмування.
При вирішенні повністю цілочислових задач лінійного програмування використовуються:
методи відсікань
методи розгалужень
наближені методи (дані допустимі рішення, хоча і в загальному випадку неоптимальні)
Невелика розмірність задачі дозволяє застосувати метод динамічного програмування і метод розтину Гоморі. Т.к. в основі останнього лежить двоїстий симплекс метод лінійного програмування, що дозволяє поряд з знаходженням рішення, виявити і чутливість моделі до зміни параметрів, то вирішимо завдання цим методом.
. Рішення завдання
програмування прибуток меблевий таблиця
Мета завдання - отримання максимального прибутку - може бути досягнута декількома способами. Математичним виразом мети є критеріальна функції L, структура якої відображає внесок кожного із способів досягнення мети. У сформульованій задачі представлено n таких способів. Під способом досягнення мети розуміється отримання інформації про розподіл ресурсів для максимізації прибутку. Коефіцієнт C j являє собою питомий прибуток застосування j-того способу досягнення мети (прибуток від продажу одного виробу j-того типу). Змінні Х j - шукані величини, що представляють собою інтенсивність використання j-того способу досягнення мети (кількість виробів j-того типу).
Для досягнення мети маємо: m- види ресурсів, bi - можливий обсяг споживання i-того ресурсу (максимальна кількість деревного ресурсу і трудового фактора). Коефіцієнт a ij - витрата i-того ресурсу для одного вироби j-того типу.
Метод Гоморі
Вирішимо задачу з нецілочисельне змінними:
Максимізувати
L (x)=60x 1 + 25x 2 + 140x 3 + 160x 4
при обмеженнях
5x 1 + x 2 + 12x 3 + 15x 4? 1 500
x 1 + 2x 2 + 6x 3 + 5x 4? 1 000
7x 1 + 5x 2 + 10x 3 + 12x 4? 3 200
x 1? 40
x 2? 120 3? 20 4 ? 20
хi? 0
Етап 1
Наведемо модель до стандартного вигляду: введемо балансові змінні x 5, x 6, x 7, x 8, x 9, x 10, x 11, що не мають фізичного сенсу для приведення нерівностей до рівності.
Максимізувати
L (x)=60x 1 + 25x 2 + 140x 3 + 160x 4
при обмеженнях
x 1 + x 2 + 12x 3 + 15x 4 + x 5=1500
3x 1 + 2x 2 + 6x 3 + 5x 4 + x 6=1000
x 1 + 5x 2 + 10x 3 + 12x 4 + x 7=3200
x 1 -x 8=40
x 2 -x 9=120 3 -x 10=20
x 4 + x 11=20 січня ... x 11? 0
Рішення системи проводиться шляхом введення штучних змінних Х i. Для виключення з базису цих змінних, їх вводять в цільову функцію з великими негативними коефіцієнтами M, що мають сенс штрафів за введення штучних змінних. Таким чином, з вихідної виходить нова M-задача.
Якщо в оптимальному рішенні М-завдання немає штучних змінних, це рішення є оптимальне рішення вихідної задачі. Якщо ж в оптимальному вирішенні M-завдання хоч одна з штучних змінних буде відмінна від нуля, то система обмежень вихідної задачі несовместна і вихідна задача нерозв'язна.
Симплекс-таблиця, яка складається у процесі вирішення, використовуючи метод штучного базису, називається розширеною. Вона відрізняється від звичайної тим, що містить два рядки для функції мети: одна - для складової L (x), а інша - для складової M. При складанні симплекс таблиці вважають, що вихідні змінні є небазисними, а додаткові (x n + m) і штучні (X i) - базисними.
Етап 2
Введемо штучні змінні x 12, x 13, x 14
x 1 + x 2 + 12x 3 + 15x 4 + x 5=1500
x 1 + 2x 2 + 6x 3 + 5x 4 + x 6=1000
x 1 + 5x 2 + 10x 3 + 12x 4 + x 7=3200
x 1 -x 8 + x 12=40
x 2 -x 9 + x 13=120 3 -x 10 + x 14=20 4+ x 11=20
Цільова функція:
L (X)=60x 1 + 25x 2 + 140x 3 + 160x 4 - Mx 12 - Mx 13 - Mx 14? max
З рівнянь висловлюємо штучні змінні:
12=40-x 1 + x 813=120-x 2 + x 914=20-x 3 + x 10
підставимо в цільову функцію:
L (X)=(60 + M) x 1 + (25 + M) x 2 + (140 + M) x 3 + (160) x 4 + (- M) x 8 + (-M) x 9 + (- M) x 10 +
