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

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

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