Поясните, в чем заключается метод северо-западного угла?

Заполнение транспортной таблицы начинаем с левого верхнего угла. В клетку (1,1) заносим наименьшее из чисел a1 и b1, т.е.

 

x11 = min {a1,b1}

 

Если a1 > b1, то х11 = b1. Это означает, что потребности первого потребителя удовлетворены полностью, и, следовательно, первый столбец таблицы заполнен.

 

Двигаемся далее по первой строке, записывая в соседнюю клетку (1,2) меньшее из чисел (а1 – b1) и b2, т.е.

 

x12 = min{(a1 - b1),b2}.

 

Если a1 < b1, то х11 = а1. Это означает, что запасы первого ПО исчерпаны, и, следовательно, первая строка заполнена. Двигаемся далее по первому столбцу, записывая в клетку (2,1) наименьшее из чисел (b1 – a1) и a2, т.е.

 

x21 = min{a2, (b1 - a1)}.

 

В случае a1 < b1 можно исключить и поставщика, и потребителя, однако при этом план получается вырожденным, поэтому считается, что выбывает только поставщик, а спрос потребителя остается неудовлетворенным и равным нулю.

 

Продолжаем этот процесс, пока все заявки не будут выполнены, запасы израсходованы.

 

17. Каким образом проверяется оптимальность плана?

Если в пределах данного многоугольника одинаковый минимальный груз имели две отрицательные клетки или более, то освобождаться может лишь одна из них, а остальные должны считаться занятыми (с нулевыми поставками), так как иначе на следующем шаге нельзя будет построить многоугольник для всех свободных клеток. Вновь полученный план перевозок X вновь проверяется на оптимальность. Для этого снова строятся многоугольники и вычисляются характеристики для каждой свободной клетки. Если среди них есть отрицательные, то по общим правилам производится переход к улучшенному плану перевозок. Если все характеристики положительные, то получен единственно возможный оптимальный план. Если наряду с положительными имеются нулевые характеристики, то говорят о возможности построения множества оптимальных планов данной задачи.

 

Какими свойствами обладает транспортная задача?

Таким образом, транспортная задача обладает следующими свойствами:

 

· Все коэффициенты при переменных xij в условиях (2) и (3) равны 1 и xij ³ 0; i = 1,2,..., m; j = 1,2,..., n.

 

· Ограничения (2) и (3) выражаются точными равенствами.

 

· Каждая неизвестная величина входит лишь в два уравнения.

 

· Условия (2) и (3) не являются линейно независимыми.

 

· Число линейнонезависимых уравнений в ограничениях (2), (3) равно (m + n – 1).

 

· Общее число переменных xij равно m · n.

 

· Число базисных переменных (или независимых переменных) равно (m + n – 1).

 

· Число свободных переменных равно: K = m* n - (m+ n -1) = (m-1) * (n -1).

 

19. Что такое оптимальный план перевозок?

План Х* = (x*ij) будем называть оптимальным, если он среди всех допустимых планов X = (xij) приводит к минимальной стоимости перевозок (L* → min)

 

20. Что такое допустимый план перевозок?

 

Будем называть любой план перевозок X = (xij) допустимым, если он удовлетворяет условиям (2), (3), что означает: все заявки удовлетворены, все запасы исчерпаны.

 

Что такое матрица перевозок?

Матрицу X будем называть матрицей перевозок или планом грузоперевозок. Заметим, что все xij ≥ 0, i = 1,..., m, j = 1,.., n.

 

22. Что такое матрица издержек?

 

Все числа Сij можно представить в виде матрицы стоимостей (или

 

расстояний):

 

 

 

Как выбирается величина, перемещаемая по клеткам?

В ее системе ограничений применяется одинаковая единица измерения для всех величин, а коэффициенты при всех переменных равны единице.