Рішення

Математична модель завдання:

(2.1)

(2.2)

(2.3)

(2.4)

де – кількість вантажу i-го виду, що потрібно розмістити на j-ому складі;

–собівартість зберігання вантажу i-го виду на j-ому складі;

–обсяг вантажопотоку;

–пропускна спроможність складу.

У табл.5 отриманий оптимальний план розподілу вантажу по складах:

X₁₁ =18 тис. т; X₂₂ =7 тис. т; X₃₁ =2 тис. т; X₃₃=22 тис. т; X₃₄ =1 тис. т; X₄₄ =15 тис. т; X₅₂ =18 тис. т; X₂₄=13 тис. т, що забезпечує мінімум витрат на зберігання: Z=314 тис. у.о.

Таблиця 2

Складання опорного плану і перевірка на оптимальність

Таблиця 3

Перерахування по циклу й перевірка на оптимальність

Таблиця 4

Перерахування по циклу й перевірка на оптимальність

Таблиця 5

Перерахування по циклу й перевірка на оптимальність

Планування оперативної діяльності підприємства шляхом застосування завдання про призначення

Завдання про призначення – окремий випадок розподільного завдання. У завданні про призначення кількість пунктів відправлення дорівнює кількості пунктів призначення. Обсяги потреби й пропозиції в кожному з пунктів призначення й відправлення дорівнюють 1. Прикладом типового завдання про призначення є розподіл працівників по різних видах робіт, мінімізуючий, допустимо, сумарний час виконання робіт.

Отже, необхідно розподілити m виконавців по n роботам. C_ij- параметр, що характеризує виконання j-ой роботи i-им виконавцем. Завдання полягає у визначенні оптимальних призначень, при яких цільова функція досягає екстремального значення

Математична модель завдання:

(1) (2)

(3)

, якщо j-та робота i-им виконавцем не виконується;

, якщо j-та робота i-им виконавцем виконується;

(4)

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

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

1. Знаходимо мінімальне значення C_ij по рядках (P_i) і віднімаємо зі значень C_ij у кожному рядку.

2. З отриманих значень C_ij* вибираємо мінімальні по стовпцях (R_j) і віднімаємо в кожному стовпці.

3. Якщо в кожному рядку й у кожному стовпці можна вибрати по одному нулю, то отриманий план є припустимим, а завдання вирішенним.

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

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

6. Пункти 4,5 повторюють, поки не буде знайдено припустиме рішення.

Якщо завдання про призначення незбалансовано (число виконавців і робіт не збігається m≠n), то необхідно додати виконавців і (або) роботи так, щоб умова балансу дотримувалася. Відсутні значення C_ij для введених виконавців і робіт приймається рівним 0. Відповідні ним клітки заповнюються в останню чергу.

У завданні на max усі елементи першої таблиці множаться на -1. Далі алгоритм аналогічний розглянутому раніше.

Завдання 1. У порту є 4 причали для перевантаження генеральних вантажів. Планується одночасний підхід 4 суден для обробки. Термін обробки (у годинах) i-го судна на j-ому причалі представлено в таблиці. Як розподілити судна по причалах, щоб загальний термін обробки був мінімальним.