Методы оптимизации.Методы решения транспортных задач линейного программирования

Цель работы:

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

Задание:

Решить исходную транспортную задачу методом потенциалов, определяя опорный план методом северо-западного угла и методом минимального  элемента.

По методу потенциалов сделать ручной просчет исходной транспортной задачи.

ai        bj	7	7	7	7	2
4	16	30	17	10	16
6	30	27	26	9	23
10	13	4	22	3	1
10	3	1	5	4	24

Постановка задачи линейного программирования:

Будем рассматривать нашу задачу как задачу линейного программирования в канонической форме, т.е.:

. Перепишем исходную задачу в соответствии с рассмотренной формой. Поскольку необходимо выполнение условия:, то матрица А будет иметь 9 строк и 20 столбцов :

  

В итоге получается, что

Таким образом, эта постановка задачи совпадает с транспортной.

Построение опорного плана:

1.  Методом минимального элемента.

ai        bj	7	7	7	7	2
4	3    16	0   30	1    17	0   10	0   16
6	0   30	0   27	6   26	0   9	0   23
10	1   13	0   4	0   22	7   3	2    1
10	3   3	7   1	0   5	0   4	0   24

Затраты на перевозку по построенному плану:

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

ai        bj	7	7	7	7	2
4	4    16	0   30	0    17	0   10	0   16
6	3   30	3   27	0   26	0   9	0   23
10	0   13	4   4	6   22	0   3	0    1
10	0   3	0   1	1   5	7   4	2   24

Затраты на перевозку по построенному плану:

Решение задачи методом потенциалов с опорным планом, построенным методом минимального элемента:

1.  итерация

ai        bj	7	7	7	7	2
4	3    16	0   30	1    17	0   10	0   16
6	0   30	0   27	6   26	0   9	0   23
10	1   13	0   4	0   22	7   3	2    1
10	3   3	7   1	0   5	0   4	0   24

a)  система потенциалов

Отсюда получаем потенциалы:

b)  проверяем систему на потенциальность

2.  итерация

ai        bj	7	7	7	7	2
4	3    16	0   30	1    17	0   10	0   16
6	0   30	0   27	6   26	0   9	0   23
10	0   13	1   4	0   22	7   3	2    1
10	4   3	6   1	0   5	0   4	0   24

a)  система потенциалов

Отсюда получаем потенциалы:

b)  проверяем систему на потенциальность

3.  итерация

ai        bj	7	7	7	7	2
4	0   16	0   30	4    17	0   10	0   16
6	0   30	0   27	3   26	3   9	0   23
10	0   13	4   4	0   22	4   3	2    1
10	7   3	3   1	0   5	0   4	0   24

a)  система потенциалов

Отсюда получаем потенциалы:

b)  проверяем систему на потенциальность

4.  итерация

ai        bj	7	7	7	7	2
4	0   16	0   30	4    17	0   10	0   16
6	0   30	0   27	0   26	6   9	0   23
10	0   13	7   4	0   22	1   3	2    1
10	7   3	0   1	3   5	0   4	0   24