Алгоритм решения задачи.

1) Расписываем математическую постановку задачи

Z = 22Ф₁₁ + 14Ф₁₂ + 26Ф₁₃ +

16Ф₂₁ + 12Ф₂₂ + 20Ф₂₃ → min

Ограничения:

2) Строим матрицу и заполняем её исходными данными.

3) В соответствии с ограничениями составляем исходный план расстановки судов (методом северо-западного угла). Количество заполненных клеток должно быть = n + m – 1= 3+2-1 = 4.

Ф₁₁=5; Ф₂₁=1; Ф₂₂=3; Ф₂₃=3

Рассчитываем потенциалы

12)0 + 18*1 = 18 > 14 ! = - 4

13)0 + 13*2 = 26 = 26

4) Обнаруженное нарушение ликвидируется путём перестановки судов по контуру.

В случае нескольких нарушений в первую очередь ликвидируется max – ое.

Для перестановки берём min количество судов в квадрате с отрицательным знаком. Это 3 судна.

Строим новую матрицу

5) После перестановки судов по контуру снова определяем оценочные числа по заполненным клеткам.

Тогда:

6) Проверяем оптимальность нового плана.

13)0 + 13*2 = 26 = 26 нарушений нет

22)- 6 + 14*1 = 8 < 12 нарушений нет.

Для полученного оптимального плана рассчитаем значение целевой функции и ограничений:

Э_опт. = 2*22 + 3*14 + 4*16 + 3*20 = 210тыс. у. е.

Э_нач. = 5*22 + 1*16 + 3*12 + 3*20 = 222тыс.у. е.

Проверка ограничений:

2 + 3 = 5

4 + 3 = 7

1 линия: 2*1,5 + 4*1,5 = 9

2 линия: 3*1 + 0 = 3

3 линия: 3*2 + 0 = 6