Відмінності між версіями «Задача оптимального розкрою матеріалів»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(→‎Задача оптимального розкрою матеріалів)
(→‎Задача оптимального розкрою матеріалів)
 
(не показано одну проміжну версію цього учасника)
Рядок 1: Рядок 1:
 
===Задача оптимального розкрою матеріалів===
 
===Задача оптимального розкрою матеріалів===
−
• На підприємстві здійснюється розкрій m різних партій ма-теріалів у обсягах <math>b_i(i=\overline{1,m})</math>  одиниць однакового розміру в кожній партії.<br>
+
• На підприємстві здійснюється розкрій <math>m</math> різних партій ма-теріалів у обсягах <math>b_i(i=\overline{1,m})</math>  одиниць однакового розміру в кожній партії.<br>
−
• Із матеріалів усіх партій потрібно виготовити максимальну кількість комп¬лектів Z, у кожен з яких входить p різних ви-дів окремих частин в кількості <math>k_r(r=\overline{1,p})</math>  одиниць,
+
• Із матеріалів усіх партій потрібно виготовити максимальну кількість комплектів <math>Z</math>, у кожен з яких входить <math>p</math> різних видів окремих частин в кількості <math>k_r(r=\overline{1,p})</math>  одиниць,<br>
 +
• враховуючи, що кожну одиницю матеріалу можна розкроїти на окремі частини <math>n</math> різними способами, <br>
 +
• причому у разі розкрою одиниці <math>i</math>-ої партії <math>j</math>-им способом отримуємо <math>a_{ijr}</math> деталей <math>r</math>-го виду.<br>
 +
 
 +
Запишемо математичну модель задачі. Позначимо через:<br>
 +
• <math>x_{ij}</math> — кількість одиниць матеріалу <math>i</math>-ої партії, що будуть розкроєні <math>j</math>-им способом.<br>
 +
• Тоді з <math>i</math>-ої партії за <math>j</math>-го способу розкрою отримаємо <math>a_{ijr}</math> <math>x_{ij}</math> деталей <math>r</math>-го виду.<br>
 +
• З усієї ж <math>i</math>-ої партії у разі застосування до неї всіх <math>n</math> способів розкрою отримаємо <math> \sum_{j=1}^n a_{ijr}  x_{ij}</math>  деталей <math>r</math>-го виду,<br>
 +
• а з усіх <math>m</math> партій їх буде отримано <math>Z_r=\sum_{i=1}^m \sum_{j=1}^n a_{ijr} x_{ij}</math>.<br>
 +
 
 +
У кожен комплект має входити <math>k_r(r=\overline{1,p})</math> деталей, тому відношення <math>Z_r/k_r(r=\overline{1,p})</math> визначає кількість комплектів, які можна виготовити з деталей <math>r</math>-го виду. Кількість повних комплектів для всіх видів деталей визначається найменшим з цих відношень.<br>
 +
 
 +
У разі повного комплекту має виконуватися рівність відношень:
 +
<center><math>Z_1/k_1=Z_2/k_2=\ldots=Z_r/k_r=\ldots=Z_p/k_p ,</math></center>
 +
 
 +
звідки <math>p</math> — 1 відношення можна виразити через будь-яке з них, наприклад, через перше:
 +
<center><math>Z_r/k_r=Z_1/k_1 </math> <math>(r=\overline{2,p})</math> або <math>Z_r=k_rZ_1/k_1 </math> <math>(r=\overline{2,p}) </math> .</center>
 +
 
 +
Замінивши  <math>Z_r</math> та <math>Z_1</math> їх значеннями, отримаємо <math>p</math> – 1 обмеження стосовно комплектів:
 +
<center><math>\sum_{i=1}^m \sum_{j=1}^n a_{ijr} x_{ij}=\frac{k_r}{k_1} \sum_{i=1}^m \sum_{j=1}^n a_{ij1} x_{ij}</math></center>
 +
<center><math>\sum_{i=1}^m \sum_{j=1}^n (a_{ijr}-\frac{k_r}{k_1} a_{ij1})x_{ij}=0, r=\overline{2,p}</math></center>
 +
 
 +
Враховуючи наявну кількість одиниць матеріалу в партіях, запишемо <math>m</math> обмежень щодо ресурсів:
 +
<center><math>\sum_{j=1}^n x_{ij}=b_j</math> <math>(i=\overline{1,m})</math>.</center>
 +
 
 +
(Обмеження щодо використання ресурсів можуть бути рівняннями чи нерівностями залежно від того, повністю чи не повністю необхідно використати наявний обсяг ресурсів).<br>
 +
Всі <math>x_{ij}</math> мають задовольняти умову невід’ємності:
 +
<math>x_{ij}\ge 0(i=\overline{1,m},j=\overline{1,n})</math>
 +
та цілочисловості.<br>
 +
Отже, необхідно знайти найбільше значення функції:
 +
<center><math>\max Z=\min_{1\le r \le p} \frac{1}{k_r}\sum_{i=1}^m \sum_{j=1}^n a_{ijr} x_{ij}</math></center>
 +
 
 +
за обмежень:
 +
<center><math>\left\{ {\begin{array}{l}
 +
\sum_{i=1}^m \sum_{j=1}^n {\left(
 +
a_{ijr}-\frac{k_{r}}{k_{1}}a_{ij1} \right)x_{ij}=0,\left( r=\overline {2,p}
 +
\right);} \\
 +
\\
 +
\sum_{j=1}^n {x_{ij}=b_{i}\left( i=\overline {1,m} \right)} \\
 +
\end{array}} \right. </math></center>
 +
 
 +
 
 +
<center><math>x_{ij}\ge 0(i=\overline{1,m},j=\overline{1,n}),</math></center>
 +
<center><math>x_{ij}</math>— цілі числа <math>(i=\overline{1,m},j=\overline{1,n})</math>.</center>

Поточна версія на 19:47, 10 травня 2012

Задача оптимального розкрою матеріалів

• На підприємстві здійснюється розкрій Неможливо розібрати вираз (невідома помилка): m 

різних партій ма-теріалів у обсягах Неможливо розібрати вираз (невідома помилка): b_i(i=\overline{1,m})
 одиниць однакового розміру в кожній партії.

• Із матеріалів усіх партій потрібно виготовити максимальну кількість комплектів Неможливо розібрати вираз (невідома помилка): Z , у кожен з яких входить Неможливо розібрати вираз (невідома помилка): p 

різних видів окремих частин в кількості Неможливо розібрати вираз (невідома помилка): k_r(r=\overline{1,p})
 одиниць,

• враховуючи, що кожну одиницю матеріалу можна розкроїти на окремі частини Неможливо розібрати вираз (невідома помилка): n 

різними способами,

• причому у разі розкрою одиниці Неможливо розібрати вираз (невідома помилка): i -ої партії Неможливо розібрати вираз (невідома помилка): j -им способом отримуємо Неможливо розібрати вираз (невідома помилка): a_{ijr} 

деталей Неможливо розібрати вираз (невідома помилка): r

-го виду.

Запишемо математичну модель задачі. Позначимо через:
• Неможливо розібрати вираз (невідома помилка): x_{ij} 

— кількість одиниць матеріалу Неможливо розібрати вираз (невідома помилка): i

-ої партії, що будуть розкроєні Неможливо розібрати вираз (невідома помилка): j -им способом.
• Тоді з Неможливо розібрати вираз (невідома помилка): i -ої партії за Неможливо розібрати вираз (невідома помилка): j -го способу розкрою отримаємо Неможливо розібрати вираз (невідома помилка): a_{ijr} 

Неможливо розібрати вираз (невідома помилка): x_{ij}
деталей Неможливо розібрати вираз (невідома помилка): r

-го виду.
• З усієї ж Неможливо розібрати вираз (невідома помилка): i -ої партії у разі застосування до неї всіх Неможливо розібрати вираз (невідома помилка): n 

способів розкрою отримаємо Неможливо розібрати вираз (невідома помилка):  \sum_{j=1}^n a_{ijr}  x_{ij}
 деталей Неможливо розібрати вираз (невідома помилка): r

-го виду,
• а з усіх Неможливо розібрати вираз (невідома помилка): m 

партій їх буде отримано Неможливо розібрати вираз (невідома помилка): Z_r=\sum_{i=1}^m \sum_{j=1}^n a_{ijr} x_{ij}

.

У кожен комплект має входити Неможливо розібрати вираз (невідома помилка): k_r(r=\overline{1,p}) 

деталей, тому відношення Неможливо розібрати вираз (невідома помилка): Z_r/k_r(r=\overline{1,p})
визначає кількість комплектів, які можна виготовити з деталей Неможливо розібрати вираз (невідома помилка): r

-го виду. Кількість повних комплектів для всіх видів деталей визначається найменшим з цих відношень.

У разі повного комплекту має виконуватися рівність відношень:

Неможливо розібрати вираз (невідома помилка): Z_1/k_1=Z_2/k_2=\ldots=Z_r/k_r=\ldots=Z_p/k_p ,

звідки Неможливо розібрати вираз (невідома помилка): p 

— 1 відношення можна виразити через будь-яке з них, наприклад, через перше:
Неможливо розібрати вираз (невідома помилка): Z_r/k_r=Z_1/k_1 
Неможливо розібрати вираз (невідома помилка): (r=\overline{2,p})
або Неможливо розібрати вираз (невідома помилка): Z_r=k_rZ_1/k_1 
Неможливо розібрати вираз (невідома помилка): (r=\overline{2,p})
.

Замінивши Неможливо розібрати вираз (невідома помилка): Z_r 

та Неможливо розібрати вираз (невідома помилка): Z_1
їх значеннями, отримаємо Неможливо розібрати вираз (невідома помилка): p
– 1 обмеження стосовно комплектів:
Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m \sum_{j=1}^n a_{ijr} x_{ij}=\frac{k_r}{k_1} \sum_{i=1}^m \sum_{j=1}^n a_{ij1} x_{ij}
Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m \sum_{j=1}^n (a_{ijr}-\frac{k_r}{k_1} a_{ij1})x_{ij}=0, r=\overline{2,p}

Враховуючи наявну кількість одиниць матеріалу в партіях, запишемо Неможливо розібрати вираз (невідома помилка): m 

обмежень щодо ресурсів:
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n x_{ij}=b_j 
Неможливо розібрати вираз (невідома помилка): (i=\overline{1,m})
.

(Обмеження щодо використання ресурсів можуть бути рівняннями чи нерівностями залежно від того, повністю чи не повністю необхідно використати наявний обсяг ресурсів).
Всі Неможливо розібрати вираз (невідома помилка): x_{ij} 

мають задовольняти умову невід’ємності:

Неможливо розібрати вираз (невідома помилка): x_{ij}\ge 0(i=\overline{1,m},j=\overline{1,n})

та цілочисловості.
Отже, необхідно знайти найбільше значення функції:

Неможливо розібрати вираз (невідома помилка): \max Z=\min_{1\le r \le p} \frac{1}{k_r}\sum_{i=1}^m \sum_{j=1}^n a_{ijr} x_{ij}

за обмежень:

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} \sum_{i=1}^m \sum_{j=1}^n {\left( a_{ijr}-\frac{k_{r}}{k_{1}}a_{ij1} \right)x_{ij}=0,\left( r=\overline {2,p} \right);} \\ \\ \sum_{j=1}^n {x_{ij}=b_{i}\left( i=\overline {1,m} \right)} \\ \end{array}} \right.


Неможливо розібрати вираз (невідома помилка): x_{ij}\ge 0(i=\overline{1,m},j=\overline{1,n}),
Неможливо розібрати вираз (невідома помилка): x_{ij}

— цілі числа Неможливо розібрати вираз (невідома помилка): (i=\overline{1,m},j=\overline{1,n})

.
Отримано з https://wiki.cusu.edu.ua/index.php?title=Задача_оптимального_розкрою_матеріалів&oldid=67723