Стандартный вид таблицы-матрицы.

Математическая постановка данной задачи:

1.

2.

3.

4.

5.

6.

7.

8.

Начальный план составим с использованием метода северо-западного угла. Здесь заполнение матрицы начинается с верхней левой клетки и продолжается вправо и вниз.

Загрузим 1-ую клетку с индексом 11.

X₁₁ = min (Q₁; V₁) = min(60, 40) = 40

X₁₂ = min( Q₁; V₂) = min(20; 60) = 20

Для каждого расчёта потенциалов и нахождения оптимального плана число заполненных клеток должно быть равно m + n-1(m=3; n=4)

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

Z =

Расчёт потенциалов выполняется по заполненным клеткам из условия выполнения следующего равенства:

ai + bj = Cij

Первый потенциал принимается произвольно: а₁ = 0

a₁ + b₁ = 1 b₁ = 1

a₁ + b₂ = 2 b₂ = 2

a₂ + b₂ = 3 a₂ = 1

a₂ + b₃ = 2 b₃ = 1

a₃ + b₃ = 2 a₃ = 1

a₃ + b₄ = 1 b₄ = 0

Признак оптимальности для метода потенциалов - это выполнение следующего неравенства:

для пустых клеток в оптимальном плане должно выполнятся

ai + bj Cij

Если для всех пустых клеток данное неравенство выполняется, то план признаётся оптимальным.

Оптимальных планов с точки зрения различных сочетаний xij может быть несколько, но значение целевой функции у всех оптимальных планов будет одинаковым.

1-3 0+1<3 2-4 1+0 0! 0=1

1-4 0+0<4 3-1 1+1 0! 0=2

2-1 1+1<4 3-2 2+1 2! 0=1

Для устранения нарушения оптимальности следует клетку с max нарушением из незаполненной сделать заполненной. Для этого строится контур перераспределения ресурсов. Этот контур представляет собой замкнутый многоугольник с вершинами в заполненных клетках за исключением клетки с вершиной max неоптимальности. Число вершин контура должно быть чётное и в каждом столбце(строке) – 2 вершины. Одна - загружается, другая- разгружается.

Чтобы узнать объём, который мы перенесли в клетку с max нарушением оптимальности, мы должны выбрать min объём из клеток контура помеченных знаком «-»

X min = min

Недостающее количество заполненных клеток (до m + n - 1) заполняем условными нулями.

Далее рассчитываем новые значения потенциалов(а₁=0)

по заполненным клеткам из равенства ai + bj = Cij.

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

Предварительно рассчитаем целевую функцию:

Z = 2*60+2*80+1*60=340у. е.

(1-3) 0+3=3 (2-2) -1+2<3

(1-4) 0+2<4 (2-4) -1+2<0

(2-1) -1+1<4 (3-2) -1+2<2

Нарушение в клетке 3-1, начиная с нее строим новый контур.

Z = 2*60+2*20+60*2=280у. е.

1-3) 0+3=3 2-2) -1+2<3

1-4) 0+1<4 3-2) -1+2<2

2-1) -1+1<4 3-4) -1+ 1<1

По всем пустым клеткам выполняется условие a_i+b_j Cij план оптимальный.

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

60=60 40=40

20+60=80 60=60

40+60=100 20+60=80

60=60