Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекция по линейному прграммированию.doc
Скачиваний:
1
Добавлен:
01.04.2025
Размер:
1000 Кб
Скачать
☆

Основные свойства тз

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

(5)

иначе будет открытая модель:

(6)

  1. ТЗ всегда имеет решение для закрытой модели.

  2. Число уравнений задачи (1)-(4) равно (m+n), а число переменных – mn.

  3. Коэффициенты при переменных в урвнениях (1) и (2) равны 1.

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

Методы построения первоначального плана

Решение транспортной задачи проводится в два этапа.

  1. На первом этапе находится первоначальный опорный план.

  2. На втором этапе на базе опорного плана методом потенциалов определяется оптимальный план.

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

Самыми простыми методами построения первоначального плана ТЗ являются:

Метод северо-западного угла (или диагональный метод).

Метод минимальной стоимости (или минимального элемента, или минимального тарифа).

Метод двойного предпочтения.

Из методов оптимизации первоначального плана самым распространенным является метод потенциалов.

Метод северо-западного угла

Рассмотрим транспортную задачу по следующим исходным данным, представленным в виде таблицы:

ПН

ПО

В1

В2

В3

В4

В5

Запасы аi

А1

4

11

6

5

15

200

А2

8

7

9

13

10

200

А3

10

5

12

7

20

100

Потребнос- ти bj

70

80

150

110

90

В методе северо-западного угла, или диагональном, заполнение транспортной таблицы всегда начинается с клетки (А1 , В1), т.е. “северо-западного угла” таблицы. Далее заполнение идет вокруг диагонали таблицы и всегда заканчивается в правом нижнем углу (клетка ( А3 , В5 )). В каждой клетке объем перевозки определяется как наименьшее значение из двух чисел: остатка запаса на базе и остатка заявки потребителя. Отсюда:

х11 = min { a1 , b1 } = { 200 ; 70 } = 70.

Таким образом, заявка первого потребителя выполняется в полном объеме, поскольку на базе имелся больший запас товара. Поэтому остальные клетки первого столбца не нужны и остаются пустыми.

Далее наступает очередь второго заказчика, который со своей заявкой приходит на первую базу, где еще остался товар:

х12 = min { 200 - 70 ; 80 } = { 130 ; 80 } = 80.

Он также получает всё, и остальные клетки второго столбца также будут пустыми.

Теперь на первой базе осталось только 50 т груза. Поэтому третий заказчик получит только эти 50 т, хотя ему требуется 150 т.

х13 = min { 200 – 70 – 80 ; 150} = 50.

Поскольку на первой базе больше не осталось товара, остальные клетки первой строки будут пустыми.

Остальную часть своего заказа второй заказчик получит на второй базе:

х23 = min { 200 ; 150 – 50 } = 100.

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

ПН

ПО

В1

В2

В3

В4

В5

аi

А1

4

70

11

80

6

50

5

15

200

А2

8

7

9

100

13

100

10

200

А3

10

5

12

7

10

20

90

100

bj

70

80

150

110

90

В этом опорном плане семь занятых клеток. Поскольку их должно быть m +n –1, где m – число баз, n - число заказчиков, план является невырожденным. Если бы клеток было меньше, чем m +n –1, план был бы вырожденным.

Осталось подсчитать общую стоимость перевозок. Она складывается из произведений объемов перевозок и тарифов по всем занятым клеткам, т.е.:

F ( X1 ) = 70  4 + 80  11 + 50  5 + 100  9 + 100  13 + 10  7 + 90  20 = 5530.

Как видим, при распределении грузов совсем не учитывается стоимость перевозок. Поэтому, как правило, метод северо-западного угла дает опорный план, далекий от оптимального.