ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1080
Скачиваний: 2
116
повторяется
в
оставшейся
части
таблицы
.
Пример
.
Транспортная
таблица
составлена
для
5
поставщиков
и
5
потребителей
.
В
правом
верхнем
углу
каждой
клетки
таблицы
указан
тариф
на
перевозку
от
поставщика
к
соответствующему
потребителю
.
Найти
опорное
решение
методом
минимальной
стоимости
.
▲
На
первых
3-
х
шагах
перевозками
в
10, 20, 30
единиц
были
заняты
соответственно
клетки
(1;5), (2;4), (3;2)
и
вычеркнуты
первые
3
строки
, 4-
й
и
5-
й
столбцы
.
Наименьший
тариф
в
оставшейся
части
таблицы
оказался
в
клетке
(4;2),
куда
и
поместили
перевозку
в
10
единиц
.
Второй
потребитель
получил
весь
продукт
.
Поэтому
вычеркиваем
2-
й
столбец
.
Среди
не
вычеркнутых
клеток
наименьший
тариф
в
клетке
(4;3).
Помещаем
в
эту
клетку
перевозку
в
30
единиц
от
4-
го
поставщика
к
3-
му
потребителю
.
Вычеркиваем
4-
ю
строку
и
3-
й
столбец
.
Затем
помещаем
перевозку
в
50
единиц
от
5-
го
поставщика
к
1-
му
потребителю
в
клетку
(5;1).
Вычеркиваем
5-
ю
строку
и
1-
й
столбец
.
Полученная
транспортная
таблица
соответствует
опорному
решению
.
■
Пусть
вектор
α
0
= (x
11
0
, …, x
mn
0
)
является
допустимым
решением
транспортной
задачи
линейного
программирования
.
Ненулевые
координаты
этого
вектора
,
т
.
е
.
х
ij
0
≠
0,
запишем
в
соответствующие
клетки
транспортной
таблицы
.
Если
окажется
,
что
заполненных
клеток
меньше
,
чем
m + n – 1,
то
в
некоторые
из
оставшихся
пустыми
клеток
транспортной
таблицы
допишем
«
жирным
»
шрифтом
нули
так
,
чтобы
образовать
ацикличный
набор
из
m+ n – 1
заполненных
клеток
.
Определение
.
Потенциалами
опорного
решения
α
0
= (x
11
0
, …, x
mn
0
)
называются
такие
числа
U
i
(i = 1, 2, … m) , V
j
(j = 1, 2, …,n) ,
что
равенство
U
i
+ V
j
= C
ij
выполняется
для
всех
занятых
клеток
.
Таким
образом
,
для
нахождения
потенциалов
опорного
решения
имеется
система
линейных
уравнений
U
i
+ V
j
= c
ij
, i = 1, 2, … m; j = 1, 2, …, n,
в
которой
m + n – 1
уравнений
и
m + n
неизвестных
.
Такая
система
является
неопределенной
и
поэтому
всегда
имеет
решение
.
Структура
системы
такова
,
что
,
задав
значение
одной
из
неизвестных
,
все
остальные
неизвестные
5 3 6 2 ‘’ 1
10 a
1
=10
4 7 3 ‘’ 1
20
2
a
2
=20
‘ 3 ‘‘ 1
30
‘ 2 5 8
a
3
=30
10 ‘ 2
10
3
30
4 7
a
4
=40
+30
9
50
12 15 4 ‘ 3
a
5
=50
b
1
=50 b
2
=40 b
3
=30 b
4
=20 b
5
=10 ai
b
j
–10
ai’
b
j
’
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
117
определяются
однозначно
.
Теорема
.(
достаточное
условие
оптимальности
опорного
решения
)
Пусть
U
i
(i =1, 2, … m) , V
j
(j =1, 2, …,n)
потенциалы
опорного
решения
α
0
= (x
11
0
, …, x
mn
0
)
транспортной
задачи
линейного
программирования
.
Если
для
всех
не
занятых
клеток
,
т
.
е
х
ij
0
= 0, i = 1, 2, …, m; j = 1, 2, …, n
выполняется
неравенство
U
i
+ V
j
≤
c
ij
,
то
опорное
решение
является
оптимальным
решением
данной
задачи
.
Решение
транспортной
задачи
линейного
программирования
методом
потенциалов
Пусть
вектор
α
1
= (x
11
1
, …, x
mn
1
)
является
опорным
решением
транспортной
задачи
линейного
программирования
.
Ненулевые
координаты
этого
вектора
,
т
.
е
.
х
ij
1
≠
0,
запишем
в
соответствующие
клетки
транспортной
таблицы
.
Если
окажется
,
что
заполненных
клеток
меньше
,
чем
m + n – 1,
то
в
некоторые
из
оставшихся
пустыми
клеток
транспортной
таблицы
допишем
«
жирным
»
шрифтом
нули
так
,
чтобы
образовать
ацикличный
набор
из
m + n –1
заполненных
клеток
.
Шаг
1
.
Найдем
потенциалы
опорного
решения
α
1
=(x
11
1
, …, x
mn
1
)
Если
для
любой
из
незаполненных
клеток
,
т
.
е
.
х
ij
1
= 0, i=1, 2, … m;
j = 1, 2, …, n,
окажется
,
что
U
i
+ V
j
≤
c
ij
,
то
α
1
=(x
11
1
, …, x
mn
1
)
является
оптимальным
решением
данной
задачи
.
Если
же
найдется
клетка
(r,s),
для
которой
выполняется
неравенство
U
r
+
V
s
> C
us
,
то
строим
цикл
,
одна
из
вершин
которого
находится
в
клетке
(r,s),
а
все
остальные
вершины
находятся
в
ранее
заполненных
клетках
.
Такой
цикл
существует
и
притом
только
один
.
Назовем
его
циклом
пересчета
.
Каждой
вершине
цикла
пересчета
,
начиная
с
вершины
(r,s),
присвоим
поочередно
положительные
и
отрицательные
знаки
,
т
.
е
.
знаки
+
и
– .
Среди
клеток
со
знаком
минус
выберем
клетку
(k,
)
с
наименьшей
величиной
перевозки
,
т
.
е
. x
k
= min{x
ij
}.
Пусть
x
k
= p.
Тогда
транспортную
таблицу
заполним
следующим
образом
:
x
ij
”
= x
ij
’
,
если
клетка
(i, j)
не
является
вершиной
цикла
пересчета
;
x
ij
”
= x
ij
’
+
р
,
если
клетке
(i, j)
был
присвоен
знак
плюс
;
x
ij
”
= x
ij
’
–
р
,
если
клетке
(i, j)
был
присвоен
знак
минус
;
клетка
(k,
)
не
заполняется
.
Можно
доказать
,
что
в
результате
будет
получено
новое
опорное
решение
α
2
=(x
11
”
, …, x
mn
”
),
на
котором
значение
целевой
функции
будет
не
меньше
,
чем
на
первоначальном
опорном
решении
,
т
.
е
. f(
α
2
)
≤
f(
α
1
).
Шаг
2
.
Выполняем
шаг
1
для
опорного
решения
α
2
=(x
11
”
, …, x
mn
”
),
и
т
.
д
.
Через
конечное
число
шагов
будет
найдено
оптимальное
решение
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
118
Пример
.
Используя
опорное
решение
,
полученное
в
предыдущем
примере
,
решить
задачу
методом
потенциалов
.
▲
Допишем
жирным
шрифтом
нули
в
клетки
(2,3). (3,1)
и
(5,5)
так
,
чтобы
получить
ацикличный
набор
из
m+n–1=
9
занятых
клеток
.
Таким
образом
,
найдено
первоначальное
опорное
решение
(
табл
. 1).
Находим
потенциалы
этого
опорного
решения
.
Для
этого
выбираем
строку
или
столбец
с
наибольшим
количеством
занятых
клеток
,
например
, 4–
юстроку
.
Присваиваем
этой
строке
потенциал
U
4
=0.
Далее
по
тарифу
c
42
,
используя
уравнение
U
4
+ V
2
= c
42
,
находим
потенциал
V
2
=2,
а
по
тарифу
с
43
=3 ,
используя
уравнение
U
4
+ V
3
= c
43
,
находим
потенциал
V
3
=3
и
т
.
д
.
находим
потенциалы
остальных
строк
и
столбцов
.
После
этого
выясняем
,
существуют
ли
клетки
,
для
которых
выполняется
неравенство
U
r
+ V
s
> c
us
.
Если
такие
клетки
существуют
,
то
величину
(U
r
+ V
s
– c
rs
)
записываем
в
левый
нижний
угол
соответствующей
клетки
.
Выбираем
клетку
с
наибольшей
из
полученных
величин
.
Т
.
к
.
все
найденные
величины
получились
одинаковыми
,
равными
2,
то
выбираем
клетку
(1,4)
с
наименьшим
тарифом
.
Строим
цикл
пересчета
с
вершинами
в
клетках
:{(1;4), (1;5), (5;5), (5;1), (3;1), (3;2), (4;2), (4;3), (2;3), (2;4), (1;4)},
в
каждую
из
которых
поочередно
ставим
плюс
и
минус
,
начиная
с
клетки
(1, 4).
Среди
клеток
со
знаком
минус
выбираем
клетку
(1, 5)
с
наименьшей
перевозкой
х
15
=10.
Далее
эту
величину
добавляем
к
перевозке
в
клетках
со
знаком
плюс
и
вычитаем
из
перевозки
в
клетках
со
знаком
минус
.
Получаем
новое
опорное
решение
(
табл
. 2),
которое
состоит
из
m+n–1 = 9
занятых
клеток
.
V
j
U
i
4 2 3 1 –2
Табл
.2
1 5
3
6 2
10
1
10
0 4 7 3
10
+
1
10 –
2
20
–
1
3
10
+
1
20 –
2 5 8
30
0 10 2
20 +
3
20 –
4 7
40
5 9
40
–
12 15 4
2 +
3
10
50
50
40
30
20
10
ai
b
j
V
j
U
i
4 2 3 1 –2
Табл
.1
3 5
2
3
2
6 2
2 +
1
10
–
10
0 4 7 3
0 +
1
20 –
2
20
–1 3
0 +
1
30 –
2 5 8
30
0 10 2
10 +
3
30 –
4 7
40
5 9
50 –
12 15 4 3
0 +
50
50
40
30
20
10
ai
b
j
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
119
Считаем
потенциалы
,
оставляя
U
4
= 0,
и
записываем
их
в
таблицу
.
Выясняем
,
что
только
для
клетки
(5,4)
выполняется
неравенство
U
r
+ V
s
> c
rs
.
При
этом
величину
(U
5
+ V
4
– c
54
) = 2
записываем
в
левый
нижний
угол
этой
клетки
.
Строим
цикл
пересчета
с
вершинами
в
клетках
:{(5;4), (5;1), (3;1), (3;2),
(4;2), (4;3), (2;3), (2;4), (5;4)}
и
расставляем
в
них
поочередно
знаки
плюс
и
минус
,
начиная
с
клетки
(5, 4).
Среди
клеток
со
знаком
минус
находим
наименьшую
величину
перевозки
х
24
=10
и
продвигаем
ее
по
циклу
пересчета
,
прибавляя
в
клетках
со
знаком
плюс
и
вычитая
в
клетках
со
знаком
минус
.
Получаем
новое
опорное
решение
(
табл
. 3)
После
вычисления
потенциалов
оказывается
,
что
данное
опорное
решение
также
не
является
оптимальным
.
Строим
цикл
пересчета
и
передвигаем
по
нему
10
единиц
груза
.
Получаем
следующее
опорное
решение
(
табл
. 4)
с
8
занятыми
клетками
.
Дописываем
«0»
жирным
шрифтом
в
клетку
(1,1),
чтобы
получить
ацикличный
набор
из
m + n – 1 = 9
клеток
.
Пересчитываем
потенциалы
.
Для
каждой
свободной
клетки
выполняется
неравенство
U
r
+
V
s
< c
rs
.
Следовательно
,
полученное
в
таблице
4
опорное
решение
является
оптимальным
.
■
Замечание
.
М
одель
транспортной
задачи
линейного
программирования
называют
открытой
,
если
m
i
1
a
i
>
n
j
1
b
j
,
или
m
i
1
a
i
<
n
j
1
b
j
.
После
введения
фиктивного
потребителя
с
объемом
потребления
b
n+1
=
n
j
1
b
j
–
m
i
1
a
i
,
или
фиктивного
поставщика
с
V
j
U
i
4 2 3 –1
–2
Табл
.3
3 5
2
3
2 +
6 2
10
–
1
10
0 4 7 3
20
1
2
20
–
1
3
20 +
1
10 –
2 5 8
30
0 10 2
30
3
10
4 7
40
5 9
30 –
12 15 4
10 +
3
10
50
50
40
30
20
10
ai
b
j
V
j
U
i
4 2 3 –1
–2
Табл
.4
1 5
0
3
10
6 2
1
10
0 4
7 3
20
1
2
20
–
1
3
30
1
2 5 8
30
0 10 2
3 0
3
10
4 7
40
5 9
20
12 15 4
20
3
10
50
50
40
30
20
10
ai
b
j
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
120
объемом
поставок
a
m+1
=
m
i
1
a
i
–
n
j
1
b
j
,
такая
задача
также
решается
методом
потенциалов
.
При
этом
тарифы
на
перевозки
равны
нулю
,
т
.
е
. c
m+1, j
= c
i, n+1
=0
для
всех
j = 1, 2, …, n
и
i = 1, 2, …m.
Ответьте
на
вопросы
1.
Сформулируйте
содержательную
постановку
транспортной
задачи
линейного
программирования
.
2.
Напишите
математическую
постановку
транспортной
задачи
линейного
программирования
.
3.
В
чем
отличие
закрытой
модели
транспортной
задачи
от
открытой
модели
?
4.
Какова
структура
матрицы
условий
транспортной
задачи
,
и
какова
размерность
этой
матрицы
?
5.
Как
связаны
между
собой
матрица
условий
транспортной
задачи
и
транспортная
таблица
?
6.
Дайте
определение
набора
клеток
транспортной
таблицы
,
образующего
цикл
.
Перечислите
свойства
цикла
.
7.
Дайте
определение
ацикличного
набора
клеток
транспортной
таблицы
и
приведите
пример
.
8.
Какова
связь
между
ацикличным
набором
клеток
транспортной
таблицы
и
соответствующей
системой
векторов
условий
транспортной
задачи
?
9.
Какие
векторы
системы
условий
транспортной
задачи
образуют
ее
базис
,
и
каков
ранг
этой
системы
векторов
?
10.
Дайте
определение
опорного
решения
транспортной
задачи
линейного
программирования
.
11.
Какие
действия
необходимо
провести
для
нахождения
базиса
опорного
решения
транспортной
задачи
линейного
программирования
?
12.
Опишите
метод
минимальной
стоимости
для
нахождения
первоначального
опорного
решения
транспортной
задачи
линейного
программирования
.
13.
Дайте
определение
потенциалов
опорного
решения
транспортной
задачи
и
способа
их
вычисления
.
14.
Сформулируйте
достаточное
условие
оптимальности
опорного
решения
транспортной
задачи
линейного
программирования
.
15.
Как
формируется
цикл
пересчета
и
какова
схема
заполнения
его
вершин
?
16.
Опишите
алгоритм
метода
потенциалов
для
нахождения
оптимального
решения
транспортной
задачи
линейного
программирования
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.