Page 208 - 4685

характеризуються змістом а (i,j) – зміст i-го компонента в j-му вигляді
вихідного матеріалу.
Потрібно визначити х (j) – кількість j-го матеріалу, що приймається для
підготовки комплексної суміші. Сукупність обмежень включає умови вигляду:
x(j) <X(j),
х(1)+ х(2)+ ...+х(п)< Y,
а (i, 1)х(1) + а (i, 2) х (2) + ... + а (i, п) х (п) > А (i).
Тут X (j) – допустима для використання кількість j-го матеріалу, Y –
загальне обмеження на масу вихідного матеріалу; А (i) – мінімальний
необхідний зміст i-го компонента в кінцевому продукті.
Оцінкою варіантів рішення задачі є сума витрат на склад матеріалів у
формованій суміші:
J = c (1) х (1) + c (2) x (2) + ... + c (п) х (n),
де c (j) – витрати на одиницю j-го матеріалу.

ЗАДАЧА ПРО РАНЕЦЬ

Хай є деякий об'єм V, який необхідно заповнити різними предметами. Є
декілька видів предметів, вони відрізняються об'ємом v(i) і цінністю c (i).
Потрібно визначити варіант заповнення предметами об'єму V, щоб їх
сумарна цінність виявилася найбільшою. Невідомі змінні задачі: х (i) – кількість
предметів i-го вигляду, вибраних для розміщення в ранці. Обмеження задачі
мають вигляд:
х (1) v (1) + х (2) v (2) + ... + х (п) v (п) < V,
х (i) > 0.
Оцінка варіантів рішення задачі – це сума х(1) c (1) + + х (2) c (2) + ... + х
(п) c (п), яка повинна мати максимальне значення.

ЗАДАЧА ПРО КОМІВОЯЖЕРА

Зазвичай ця задача формулюється таким чином. Комівояжер повинен
побувати у ряді міст. Відомі відстані між кожною парою міст (час або вартість
проїзду). Необхідно вибрати найкоротший маршрут, що проходить один раз
через кожне місто. Якщо відстань між містами не залежить від напряму руху, то
завдання називається симетричним. Якщо вартість проїзду змінюється при
зміні напряму руху, завдання називається несиметричним.
Для завдання комівояжера, при двох містах, вибору немає. При трьох
містах і заданому початковому пункті можливі два маршрути. Якщо міст є
чотири, то є шість маршрутів, а вже при 11 містах – понад три з половиною
мільйони допустимих маршрутів. У загальному випадку при п містах є (n – 1)!
маршрутів.
До подібного типу завдань зводиться безліч реальних ситуацій. Це вибір
черговості обробки різнорідних виробів, вибір маршруту автотранспорту,
завдання вибору маршруту в мережах в системах зв'язку.

204