Задача оптимального розкрою ДСП

Плити розміром 350´175 см підлягають розкрою на заготовки двох типорозмірів: 200´70 і 160´90 см. Необхідно отримати не менше 300 заготовок першого і не менше 400 заготовок другого типорозмірів за умови, що сумарна кількість витрат (за площею) має бути мінімальною.

Розглянемо можливі варіанти розкрою.

Таким чином, необхідно вияснити, скільки плит необхідно розкроїти для кожного з розглянутих варіантів з умовою забезпечення вимоги геометричних розмірів заготовок, їх кількості та сумарна кількість відходів за площею має бути мінімальною.

Позначимо:

х₁ – кількість плит, що розкроюються за 1-м варіантом;

х₂ – за 2-м варіантом;

х₃ – за 3-м варіантом.

Складаємо обмеження для випуску заготовок 1-го типу розміру

(1)

(2)

Вираз для сумарної кількості відходів характеризується мінімізацією цільової функції і має вигляд

18850х1+18450х2+18050х3 ® min (3)

Необхідно також врахувати звичайні обмеження на невід’ємність величин

х₁³0; х₂³0; х₃³0. (4)

Сукупність рівнянь (1)-(4) є математичною моделлю даної задачі, а саме задачі лінійного програмування (ЗЛП.).

2. Загальна постановка задачі лінійного програмування

Нехай маємо n змінних х₁, х₂,..., х_n. Необхідно знайти такі їх значення, для яких цільова функція

. (5)

Причому змінні мають задовольняти ряду обмежень, які характеризуються наступними типами:

(6)

(7)

(8)

Також мають місце тривіальні або прості обмеження

х₁³0; х₂³0;... х_n³0. (9)

§ обмеження виду (8) легко зводяться до (7), або навпаки шляхом множення на ±1.

§ обмеження (6) можна звести до (7) шляхом виключення будь-якої змінної.

Приклад.

Якщо врахувати х₃³0, то отримаємо

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

Оптимальним розв’язком ЗЛП називається такий її допустимий розв’язок, для якого цільова функція досягає екстремум (max або min), залежно від умов задачі.

Приклад.

х₁³0; х₂³0.

Допустимі значення х₁ = 0,5; х₂ = 1.

W =3·0.5+2·1=3.5

Оптимальні розв’язки х_1опт = 7/13; х_2опт = 24/13; W =69/13.

Таким чином, ЗЛП в загальному вигляді можна записати у наступному вигляді:

. (10)

(11)

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

х₁³0; х₂³0;... х_n³0.

4. Основна задача лінійного програмування (ОЗЛП) та її властивості

Загальний вигляд ОЗЛП записується

. (12)

(13)

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

х₁³0; х₂³0;... х_n³0.

Всі нетривіальні обмеження мають вигляд рівностей

Теореми лінійної алгебри дають можливість вирішити питання про існування допустимого розв’язку ОЗЛП.

Нехай

r – число лінійно незалежних рівнянь (r – це ранг системи рівнянь)

r ≤ n;

Якщо r = n, тоді система (13) має єдиний розв’язок ® ОЗЛП має єдиний розв’язок ().

Якщо , х_і³0, то () є допустимим та оптимальним розв’язком ОЗЛП.

Якщо , х_і<0, то ОЗЛП не має допустимих розв’язків.

Якщо r < n, тоді система рівнянь (13) має нескінченне число розв’язків. Тоді n-r-змінним можна надати довільні значення і вони називаються вільними.

Для існування допустимих розв’язків ОЗЛП необхідно, щоб серед множини розв’язків системи рівнянь були невід’ємні, які задовольняють обмеженням (13).

Задачу ЛП можна звести до ОЗЛП (ЗЛП®ОЗЛП) таким чином:

введемо додаткові змінні у₁, у₂,..., у_m

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

з (11) витікає, що у₁³0, у₂³0,..., у_m³0. Отже, отримуємо ОЗЛП з більшим числом змінних, а саме n+m

ОДР, якщо вона існує, є випуклий багатокутник, а оптимальний розв’язок завжди досягнеться в одній з вершин цього багатокутника.

Допустимий розв’язок, що знаходиться в одній з вершин багатокутника, називається опорним розв’язком, а сама вершина – опорною точкою.

Для знаходження оптимального розв’язку можна перебрати всі опорні розв’язки, відшукати серед них цей, в якого цільова функція досягає

Лекція 4

ТРАНСПОРТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ (ТЗЛП)

Математична модель ТЗЛП

Приклад:

Постачальник	Споживач
Позначення	Запас вантажу	В₁	В₂	В₃	В₄
А₁	а₁=35	х₁₁		х₁₂		х₁₃	х₁₄
А₂	а₂=45	х₂₁		х₂₂		х₂₃	х₂₄
А₃	а₃=50	х₃₁		х₃₂		х₃₃	х₃₄
Потреба у вантажі	b₁=30	b₂=10	b₃=65	b₄=25

Запаси вантажу у 3 пунктах: а₁, а₂, а₃. Необхідно відправити 4 заявникам В₁, В₂, В₃, В₄.

Причому: а₁+а₂+а₃=b₁+b₂+b₃+b₄=130

Відома вартість перевезення вантажу.

Необхідно:

· визначити, скільки вантажу має отримати кожен споживач В_i від кожного виробника A_j;

· необхідно виконати заявки всіх споживачів В_і;

· вивести вантаж від усіх виробників А_j;

· забезпечити якнайменші (min) витрати на перевезення вантажу.

Позначимо: х_і – кількість одиниць вантажу при перевезенні від виробника А_і до споживача B_j. Це шукані змінні.

Запишемо умову виконання заявки споживачів В_і:

B₁: х₁₂+х₂₂+х₃₂=10

B₂: х₁₃+х₂₃+х₃₃=65

B₃: х₁₄+х₂₄+х₃₄=25.

Запишемо обмеження: (вивести весь вантаж)

Для отримання цільової функції необхідно додати витрати на перевезення по всіх маршрутах:

, і=1, 2, 3; j=1, 2, 3, 4.

Математична модель транспортної задачі. Метод найменшого елемента.

; min вартість .

Найменша вартість (3,3) записуємо 40 (50-10)

Переходимо далі

Загальний вигляд

Маємо: m – постачальників;

n – споживачів

Постачальники	Споживачі
Позначення	Запас вантажу	В₁	В₂	…	В_j	…	В_n
А₁	а₁	c₁₁	c₂₁	…	c_2ij	…	c₁_n
А₂	а₂	c₂₁	c₂₂	…	c_2j	…	c₂_n
...	…	…	…	…	…	…	…
А_і	а_i	c_i1	c_i2	…	c_ij	…	c_in
...	…	…	…	…	…	…	…
А_m	a_m	c_m1	c_m2	…	c_mj	…	c_mn
Потреба у вантажі	b₁	b₂	…	b_j	…	b_n

Умова задовільнення заявки кожного споживача B_j

. (*)

Умова вивезення вантажу від кожного A_j

. (**)

(***)

, , . (****)

Відкрита модель ТЗ

У випадку, коли сумарний запас вантажу рівний сумарній потребі у ньому, тобто , модель ТЗ є закритою (ЗТЗ). Коли ж , модель ТЗ є відкритою (ВТЗ).

Розглянемо варіанти ВТЗ.

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

Умова на вивезення вантажу: замість (**) отримаємо

, .

Умова на потреби споживачів (*), мета (***) та умова на невід’ємні значення (****) залишаються як в ЗТЗ.

2) загальна потреба перевищує сумарний запас (запаси менші за потребу)

тоді умова на вивезення (**), мета (***) та умова на невід’ємні значення (****) залишаються як в ЗТЗ.

Зазначимо, що ВТЗ зводяться до ЗТЗ.

Для 1-го варіанту: вводимо m+1 фіктивний виробник A_m₊₁ з запасом вантажу , а . Отримуємо ЗТЗ.

Для 2-го варіанту: вводимо фіктивний n+1 споживач B_n₊₁, зокрема з потребою , а . Отже, отримуємо ЗТЗ.

2. Приклади ТЗ в деревообробці

2.1. Задача оптимального розміщення виробництва

Нехай є m пунктів будівництва підприємств, які виробляють певну продукцію. Витрати на виробництво одиниці продукції в i-му пункті рівні а_і, а максимально можливий об’єм її випуску складає b_i одиниць в рік, і=1...m. Випущена продукція має бути розподілена між n споживачами.

Вартість перевезення одиниці продукції від і-го виробника до j-го споживача рівна с_ij, i=1...m, j=1…n. Необхідність у продукції (потреба) для j-го споживача складає d_j одиниць в рік.

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

Позначимо: y_i – шуканий об’єм випуску продукції в і-му пункті; х_ij – об’єм перевезення продукції від і-го пункту виробництва до j-го споживача.

Обмеження на виробництво продукції:

, .

Вся вироблена продукція має бути вивезена:

Заявка кожного споживача має бути виконана:

Крім того, об’єми виробництва і перевезень невід’ємні:

; , , .

Річні витрати на виробництво і перевезення продукції мають бути якнайменші (функція мети):