На головну

Завдання про розкрої матеріалів.

  1.  III. Завдання 3.
  2.  V2: Загальна задача нелінійного програмування
  3.  Безпечна організація при складуванні матеріалів.
  4.  ВИДИ І ЗАХИСНІ ВЛАСТИВОСТІ ТАРИ ТА ПАКУВАЛЬНИХ МАТЕРІАЛІВ.
  5.  Питання 2: Завдання та методи роботи жіночої консультації.
  6.  Питання №20. Синтетичний і аналітичний облік матеріалів.
  7.  Гідрофізичні властивості матеріалів.

На розкрій (розпил, обробку) надходить матеріал одного зразка в кількості А одиниць. Потрібно виготовити з нього L різних комплектуючих виробів в кількостях, пропорційних числах b1, b2, ... bl (Умова комплектності). Кожна одиниця матеріалу м.б. розкроєна N різними способами, причому використання i-го способу (i = 1,2, ..., n) дає аik одиниць k-го вироби (к = 1,2, ..., l).

Необхідно знайти план розкрою, що забезпечує макс число комплектів.

Складемо ЕММ завдання:

Позначимо Хi - число одиниць матеріалу розкроюємо i-им способом, і Х - число виготовляються комплектів виробів. Оскільки загальна кількість матеріалу дорівнює сумі його одиниць, розкроюємо різними способами, то

 (2.1)

Вимога комплектності виразиться рівняннями

 (K = 1,2, ..., l) (2.2)

Очевидно, що Хi> =) (i = 1,2, ..., n) (2.3)

ЕММ завдання: знайти таке рішення Х = (х1, х2, ..., хn), яке задовольняє системі рівнянь (2.1) - (2.2) і умові (2.3), при якому функція F = х приймає макс значення.

Це завдання можна узагальнити на випадок m розкроюємо матеріалів.

Нехай кожна одиниця j-го матеріалу (j = 1, 2, ..., m) може бути розкроєна N різними способами, причому використання i-го способу (i = 1,2, ..., n) дає аijk одиниць k-го вироби (к = 1,2, ..., l), а запас j-го матеріалу дорівнює Aj одиниць.

Позначимо Хij - число одиниць j-го матеріалу розкроюється i-им способом.

ЕММ завдання про розкрої матеріалів в загальній постановці набуде вигляду: знайти таке рішення Х = (х11, х12, ..., хnm), яке задовольняє системі

 (J = 1, 2, ..., m),

 (K = 1,2, ..., l)

і умові Xij> = 0, при якому функція F = х приймає макс значення.

Розглянуті приклади завдань лінійного програмування дозволяють сформулювати спільне завдання лінійного програмування.

Дана система m лінійних рівнянь і нерівностей з n змінними

 А11 * Х1 + А12 * Х2 + ... + А1N * Xn <= В1

а21 * Х1 + а22 * Х2 + ... + а2n * Xn <= В2

...............................

АК1 * Х1 + АК2 * Х2 + ... + акn * Xn <= В к

ак + 1,1 * Х1 + ак + 1,2 * Х2 + ... + а до + 1, n * Xn = В до + 1 (1)

а до + 2,1 * Х1 + а до + 2,2 * Х2 + ... + а до + 2, n * Xn = В до + 2

...............................

аm1 * Х1 + аm2 * Х2 + ... + аmn * Xn = Вm

і лінійна функція

F = С1 * Х1 + С2 * Х2 + ... + Сn * Xn (2)

Знайти таке рішення системи Х = (Х1, Х2, ..., Xj, ..., Хn), де

Хj> = 0 (j = 1, 2, ..., l; l <= n) (3)

при якому лінійна функція F (2) приймає оптимальне (макс або мін) значення.

Система (1) називається системою обмежень, а функція F - лінійною функцією, лінійної формою, цільовою функцією або функцією мети.

Більш коротко загальну задачу лінійного програмування можна представити у вигляді:

F =  a max (min)

При обмеженнях:

 (I = 1, 2, ..., k)

 (I = k + 1, k + 2, ..., m)

Хj> = 0 (j = 1, 2, ..., l; l <= n)

оптимальним рішенням (або оптимальним планом) Завдання ЛП називається рішення Х = (Х1, Х2, ..., Xj, ..., Хn) системи обмежень (1), при якому лінійна функція (2) приймає оптимальне (макс або мін) значення.

Терміни «рішення» і «план» - синоніми, проте перший використовується частіше, коли мова йде про формальну сторону завдання (її математичному рішенні), а другий - про змістовний бік (економічної інтерпретації).

За умови, що всі змінні невід'ємні (Хj> = 0, j = 1, 2, ..., n), система обмежень (1) складається лише з одних нерівностей, - таке завдання ЛП називається стандартної; якщо система обмежень (1) складається з одних рівнянь, то завдання називається канонічної. У наведених вище прикладах завдання 1 - стандартна, 2 - канонічна. Буває - загальна.

Будь-яке завдання ЛП м.б. зведена до канонічної, стандартної або загальної.

Допоміжна теорема (Без доведення):

Всякому рішенням нерівності

аi1 * Х1 + аi2 * Х2 + ... + аin * Xn <= Вi (4)

відповідає певне рішення рівняння

аi1 * Х1 + аi2 * Х2 + ... + аin * Xn + Хn + i = Вi (5)

в якому Хn + i> = 0 I = 1, m (6)

і, навпаки, кожному рішенню рівняння (5) і нерівності (6) відповідає певне рішення нерівності (4).


Використовуючи цю теорему, можна уявити стандартну задачу (1.4) - (1.6) в канонічному вигляді. З цією метою в кожне з m нерівностей в системі обмежень (1.4) вводяться додаткові невід'ємні змінні Xn + 1, Xn + 2, Хn + m і система обмежень набуде вигляду:

 А11 * Х1 + А12 * Х2 + ... + А1N * Xn + Xn + 1 = В1

а21 * Х1 + а22 * Х2 + ... + а2n * Xn + Xn +2 = В2 ............................. .........................................

аm1 * Х1 + аm2 * Х2 + ... + аmn * Xn + Xn + m = Вm

Зауваження. У розглянутій задачі все нерівності виду <=, тому додаткові невід'ємні змінні вводилися зі знаком «+». У разі нерівності виду> = відповідні додаткові невід'ємні змінні вводилися б зі знаком «-».

 




 лінійне програмування |  Геометричний сенс рішень нерівностей, рівнянь і їх систем |  Є опуклим багатокутником (або опуклою багатокутної областю). |  Властивості задач ЛП |  Геометричний метод розв'язання задач ЛП |  симплексний метод |  Знаходження оптимуму лінійної функції |  Особливі випадки симплексного методу |  сімплексні таблиці |

© um.co.ua - учбові матеріали та реферати