Page 207 - 4685

ЗАДАЧА ПРО ПРИЗНАЧЕННЯ

Нехай є п робіт і п кандидатів для їх виконання. Призначенню i-го
кандидата (i=1, …, n) на j-ю роботу (j=1, …, n) відповідає певна ефективність
(прибуток, продуктивність) або витрати якого-небудь ресурсу c . Потрібно
ij
знайти такі призначення кандидатів на всі роботи, які забезпечать найбільшу
ефективність, тобто мінімум сумарних витрат або максимум прибули
(продуктивності). Кожного кандидата можна призначити лише на одну посаду,
і кожна робота може бути виконана лише одним кандидатом.
Математична постановка задачі має вигляд:
> >
; 4 = 1; ; 4 = 1
= =
! =!
де x – шукана змінна, x = 1, якщо і-й кандидат розподіляється на j-у
ij
ij
роботу; 0 – в іншому випадку.
У такій постановці ця задача належить до класу комбінаторики.

ТРАНСПОРТНА ЗАДАЧА

Транспортна задача – це задача про вибір плану перевезень гомогенного
продукту від пунктів виробництва до пунктів споживання. Нехай є m пунктів
відправлення і п пункти призначення. Ресурси продукту в пунктах відправлення
позначимо через a(і), потребу в продукті в пункті споживання – b(j). Витрати на
доставку одиниці продукту від постачальника і до користувача j дорівнюють
c(i,j).
Балансова умова виробництва і споживання має вигляд:
а (1) + а (2) + ....+ а (п) = b (1) + b (2) +,..,+ b (т).
Потрібно визначити х (i,j) – кількість продукту, який доставляється від
пункту виробництва і до пункту споживання j. Обов'язковими умовами є:
необхідність вивезення всього виробленого продукту – х(і, 1) + х (і,
2) + ... + х (і, т) = a (i) для всіх значень і;
необхідність задоволення всіх споживачів – х (1,j) + х (2,j) + ... + х
(n,j) = b (i) для всіх значень j.
Оптимальний план постачання продукту повинен забезпечити мінімум
загальної суми витрат на доставку:

; ; < A, H4 A, H
=
Вирішуються транспортні задачі методами лінійного програмування.

ЗАДАЧА СКЛАДАННЯ СУМІШЕЙ

Задачі складання раціону корму, складу шихти при виплавці сталі, складу

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

203