Составители:
Рубрика:
транспортной матрицы записаны подлежащие определению
искомые переменные x
ij
и заданные значения удельных стоимостей
передачи мощности z
ij
.
Каждая i-я строка матрицы cоответствует уравнению баланса
мощности i-го источника питания, каждый j-й столбец - уравнению
баланса мощности j-го потребителя.
Исходное допустимое решение может быть получено по
алгоритму минимальной удельной стоимости:
1. В транспортной матрице выбирается клетка с минимальным
значением z
ij
. Если имеется несколько таких клеток, то выбирается
любая из них.
2. В выбранную клетку в качестве базисной переменной
заносится наименьшая из двух величин A
i
или B
j
, т.е. x
ij
=min(A
i
,B
j
).
При этом выполняется баланс мощности по строке i или столбцу j, в
которые входит переменная x
ij
.
3. В остальные клетки строки i или столбца j, для которых
выполнен баланс мощности, заносятся нули, соответствующие
свободным переменным. Большая из двух величин A
i
и B
j
условно
заменяется разностью этих двух величин.
4. Из оставшихся незаполненных клеток транспортной
матрицы вновь выбирается клетка с минимальным значением z
ij
. Далее
пункты 2 и 3 повторяются до полного заполнения всех клеток
транспортной матрицы.
Следует напомнить, что общее количество переменных
составляет nm. Количество отличных от нуля базисных
переменных составляет (n+m-1). Количество равных нулю свободных
переменных составляет (nm-(n+m-1)).
Пример 4. Найти допустимое решение для задачи примера 3 при
следующих исходных данных:
A
1
=50, A
2
=30, B
1
=20, B
2
=25, B
3
=35 е.м.
z
11
=1,2; z
12
=1,8; z
13
=1,5;
z
21
=1,6; z
22
=2,3; z
23
=2,1 у.е./е.м.
Решение. Изобразим транспортную матрицу размерностью 2х3
(табл. 3.2) и будем заполнять ее в соответствии с алгоритмом
минимальной удельной стоимости.
В транспортной матрице выбирается клетка с минимальным
значением z
ij
. Это клетка с переменной x
11
и удельной стоимостью
z
11
=1,2.
35
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
