Составление транспортной матрицы

Для решения данной задачи, используем табличную форму записи. В этом случае ограничения (3.2) и (3.2а) записываются в виде транспортной матрицы размерностью nm.

Таблица 4.1

				Z

Справа указаны заданные мощности источников ; и , снизу – заданные мощности потребителей , , и , справа внизу – значение целевой функции Z. Непосредственно в клетках транспортной матрицы записаны подлежащие определению искомые переменные и заданные значения удельных стоимостей передачи мощности .

Каждая -я строка матрицы соответствует уравнению баланса мощности -го источника питания, каждый -й столбец – уравнению баланса мощности -го потребителя. Исходное допустимое решение может быть получено по алгоритму минимальной удельной стоимости.

Изобразим транспортную матрицу размерностью 3×4 (табл. 3.2) и будем заполнять ее в соответствии с алгоритмом минимальной удельной стоимости.

В транспортной матрице выбирается клетка с минимальным значением . В данной задаче, таких клеток четыре – это клетка с переменной , , и , удельная стоимость которых равна единице. Просмотрим несколько вариантов допустимого решения:

Получение допустимого решения

Вариант №1.

Выберем клетку с переменной с удельной стоимостью =1.

Таблица 4.2

=30 =1	=0 =2	=20 =3	=0 =5	=50
=0 =4	=20 =1	=20 =1	=0 =2	=40
=0 =1	=0 =2	=10 =5	=50 =10	=60
=30	=20	=50	=50	Z=680

В эту клетку в качестве базисной переменной заносим меньшее из двух значений мощностей = min ( =50, =30)=30. Баланс для 1-го столбца (1-го потребителя) выполнен (30=30). В остальные клетки этого столбца заносим нули (свободные переменные =0, =0).

Поскольку от источника отобрано 30 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 50-30=20.

В следующую клетку транспортной матрицы с наименьшей удельной стоимостью =1 в качестве базисной переменной заносим меньшее из двух значений мощностей =min ( =40, =20)=20. Баланс для 2-го столбца (2-го потребителя) выполнен (20=20). В остальные клетки этого столбца также заносим нули (свободные переменные =0 и =0).

Поскольку от источника отобрано 20 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 40-20=20.

В следующую клетку транспортной матрицы с наименьшей удельной стоимостью =1 в качестве базисной переменной заносим меньшее из двух значений мощностей =min ( =20, =50)=20. Баланс по первому, по второму столбцу и по второй строке выполнен.

Поскольку потребителю поставлено 20 е.м., недостающая мощность этого потребителя условно заменяется величиной 50-20=30

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью =3. В качестве базисной переменной в эту клетку заносится меньшее из двух значений мощностей = min ( =20, =30)=20. В остальные клетки этой строки заносим нули (свободные переменные =0 и =0). Баланс по первой строке выполнен.

Поскольку потребителю поставлено 40 е.м., недостающая мощность этого потребителя условно заменяется величиной 50-40=10

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью =5. В качестве базисной переменной в эту клетку заносится меньшее из двух значений мощностей = min ( =60, =10)=10 Баланс по третьему столбцу выполнен.

Последнее значение заносится в оставшуюся незаполненную клетку транспортной матрицы в качестве базисной переменной =50.

Итак, вся транспортная матрица заполнена. Балансы мощности по строкам (по узлам источников) и по столбцам (по узлам потребителей) выполняются. Все переменные неотрицательны. Полученное исходное решение является допустимым. В этом решении:

свободные переменные: =0, =0, =0, =0, =0, =0.

базисные переменные: =30, =20, =20, =20, =10, =50. Значение целевой функции:

Z = + + + + + + + + +

+ + + .

Z = 30·1+0·2+20·3+0·5+0·4+20·1+20·1+0·2+0·1+0·2+10·5+50·10=680 у.е

(40) (60)

(50)

20 10 50

30

20

20

(50)

(30) (20) (50)

Рис. 4.2. Схема электрической сети, отвечающая допустимому решению.

В полученном допустимом решении видно, что значение целевой функции достаточно высокое Z= 680 у.е., и только один потребитель из четырех - , имеет дополнительный источник питания.

Вариант №2.

Выберем клетку с переменной с удельной стоимостью =1.

Таблица 4.3

=0 =1	=20 =2	=10 =3	=20 =5	=50
=0 =4	=0 =1	=40 =1	=0 =2	=40
=30 =1	=0 =2	=0 =5	=30 =10	=60
=30	=20	=50	=50	Z=540

В эту клетку в качестве базисной переменной заносим меньшее из двух значений мощностей = min ( =60, =30)=30. Баланс для 1-го столбца (1-го потребителя) выполнен (30=30). В остальные клетки этого столбца заносим нули (свободные переменные =0, =0).

Поскольку от источника отобрано 30 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 60-30=30.

В следующую клетку транспортной матрицы с наименьшей удельной стоимостью =1 в качестве базисной переменной заносим меньшее из двух значений мощностей =min ( =40, =50)=40. Баланс для 2-й строки выполнен. В остальные клетки этой строки заносим нули, т.к от источника мощности отобрано 40 е.м., и он равен нулю (свободные переменные =0, =0 и =0).

Поскольку потребителю поставлено 40 е.м., недостающая мощность этого потребителя условно заменяется величиной 50-40=10

В следующую клетку транспортной матрицы с наименьшей удельной стоимостью =2 в качестве базисной переменной заносим меньшее из двух значений мощностей =min ( =50, =20)=20. Баланс для второго столбца (2-го потребителя) выполнен (20=20). В остальные клетки этого столбца заносим нули (свободные переменные =0, =0).

Поскольку от источника отобрано 20 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 50-20=30.

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью =3. В качестве базисной переменной в эту клетку заносится меньшее из двух значений мощностей = min ( =30, =10)=10. Баланс для третьего столбца (3-го потребителя) выполнен (10+40=50). В остальные клетки этого столбца заносим нули (свободные переменные =0).

Поскольку от источника отобрано еще 10 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 30-10=20.

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью =5. В качестве базисной переменной в эту клетку заносится меньшее из двух значений мощностей = min ( =20, =50)=20 Баланс для первой строки выполнен. (свободные переменные =0).

Последнее значение заносится в оставшуюся незаполненную клетку транспортной матрицы в качестве базисной переменной =30.

Итак, вся транспортная матрица заполнена. Балансы мощности по строкам (по узлам источников) и по столбцам (по узлам потребителей) выполняются. Все переменные неотрицательны. Полученное исходное решение является допустимым. В этом решении:

свободные переменные: =0, =0, =0, =0, =0, =0.

базисные переменные: =20, =10, =20, =40, =30, =30. Значение целевой функции:

Z = + + + + + + + + +

+ + + .

Z = 0·1+20·2+10·3+20·5+0·4+0·1+40·1+0·2+30·1+0·2+0·5+30·10=540 у.е.

(40) (60)

(50)

20

10 30

30 20 40

(50)

(30) (20) (50)

Рис. 4.3. Схема электрической сети, полученному допустимому решению.

Во втором варианте полученного допустимого решения, можно заметить существенную разницу между значением целевой функции 1-го варианта Z =680 у.е, и 2-го Z =540. Значение целевой функции уменьшилось на 140 у.е. Согласно схеме электрической сети уже два потребителя и имеют дополнительный источник питание, но потребители по прежнему с одним источником питания.

Вариант №3.

Выберем клетку с переменной с удельной стоимостью =1.

Таблица 4.4

=0 =1	=0 =2	=10 =3	=40 =5	=50
=0 =4	=0 =1	=40 =1	=0 =2	=40
=30 =1	=20 =2	=0 =5	=10 =10	=60
=30	=20	=50	=50	Z=440

В эту клетку в качестве базисной переменной заносим меньшее из двух значений мощностей = min ( =60, =30)=30. Баланс для 1-го столбца (1-го потребителя) выполнен (30=30). В остальные клетки этого столбца заносим нули (свободные переменные =0, =0).

Поскольку от источника отобрано 30 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 60-30=30.

В следующую клетку транспортной матрицы с наименьшей удельной стоимостью =1 в качестве базисной переменной заносим меньшее из двух значений мощностей =min ( =40, =50)=40. Баланс для 2-й строки выполнен. В остальные клетки этой строки заносим нули, т.к от источника мощности отобрано 40 е.м., и он равен нулю (свободные переменные =0, =0 и =0).

Поскольку потребителю поставлено 40 е.м., недостающая мощность этого потребителя условно заменяется величиной 50-40=10

В следующую клетку транспортной матрицы с наименьшей удельной стоимостью =2 в качестве базисной переменной заносим меньшее из двух значений мощностей =min ( =30, =20)=20. Баланс для второго столбца (2-го потребителя) выполнен (20=20). В остальные клетки этого столбца заносим нули (свободные переменные =0, =0).

Поскольку от источника отобрано еще 20 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 30-20=10.

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью =3. В качестве базисной переменной в эту клетку заносится меньшее из двух значений мощностей = min ( =50, =10)=10. Баланс для третьего столбца (3-го потребителя) выполнен (10+40=50). В остальные клетки этого столбца заносим нули (свободные переменные =0).

Поскольку от источника отобрано 10 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 50-10=40.

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью =5. В качестве базисной переменной в эту клетку заносится меньшее из двух значений мощностей = min ( =40, =50)=40 Баланс для первой строки выполнен. (свободные переменные =0 и =0).

Последнее значение заносится в оставшуюся незаполненную клетку транспортной матрицы в качестве базисной переменной =10.

Итак, вся транспортная матрица заполнена. Балансы мощности по строкам (по узлам источников) и по столбцам (по узлам потребителей) выполняются. Все переменные неотрицательны. Полученное исходное решение является допустимым. В этом решении:

свободные переменные: =0, =0, =0, =0, =0, =0.

базисные переменные: =10, =40, =40, =30, =20, =10. Значение целевой функции:

Z = + + + + + + + + +

+ + + .

Z = 0·1+0·2+10·3+40·5+0·4+0·1+40·1+0·2+30·1+20·2+0·5+10·10=440 у.е.

(40) (60)

(50)

40

10

30 20 10 40

(50)

(30) (20) (50)

Рис. 4.4. Схема электрической сети, полученному допустимому решению.

Из полученного нами результата решения, можно сделать вывод, что за исключением уменьшения значения целевой функции еще на 100 у.е., существенных изменений в схеме электрической сети нет. Потребители и по прежнему остаются без дополнительного источника питания.

Вариант №4.

Выберем клетку с переменной с удельной стоимостью =1.

Таблица 4.5

=15 =1	=0 =2	=20 =3	=15 =5	=50
=0 =4	=10 =1	=30 =1	=0 =2	=40
=15 =1	=10 =2	=0 =5	=35 =10	=60
=30	=20	=50	=50	Z=575

В эту клетку в качестве базисной переменной заносим 15 е.м.,

Поскольку от источника отобрано 15 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 50-15=35. А недостающая мощность потребителя , составит 30-15=15 е.м.

В следующую клетку транспортной матрицы с наименьшей удельной стоимостью =1 в качестве базисной переменной заносим от источника мощности –недостающие потребителю - 15 е.м. Баланс для 1-го столбца выполнен. В остальные клетки этого столбца заносим нули, (свободные переменные =0,).

Поскольку от источника отобрано 15 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 60-15=45.

В следующую клетку транспортной матрицы с наименьшей удельной стоимостью =1 в качестве базисной переменной заносим от источника мощности потребителю – 10 е.м.

Поскольку от источника отобрано 10 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 40-10=30.

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью =1. В качестве базисной переменной в эту клетку заносится от источника мощности – 30 е.м. потребителю - 30 е.м. Баланс по второй строке выполнен. В остальные клетки этой строки заносим нули (свободные переменные =0 и =0).

Поскольку потребителю поставлено 30 е.м., недостающая мощность этого потребителя условно заменяется величиной 50-30=20

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью =2. В качестве базисной переменной в эту клетку заносится меньшее из двух значений мощностей = min ( =45, =10)=10 Баланс для второго столбца выполнен. В остальные клетки этого столбца заносим нули (свободные переменные =0).

Поскольку от источника отобрано еще 10 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 45-10=35.

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью =3. В качестве базисной переменной в эту клетку заносится меньшее из двух значений мощностей = min ( =35, =20)=20 Баланс для третьего столбца выполнен. В остальные клетки этого столбца заносим нули (свободные переменные =0).

Поскольку от источника отобрано еще 15 е.м., отходящих к потребителю , мощность этого источника условно заменяется величиной 35-20=15.

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью =5. В качестве базисной переменной в эту клетку заносится меньшее из двух значений мощностей = min ( =15, =50)=15.

Последнее значение заносится в оставшуюся незаполненную клетку транспортной матрицы в качестве базисной переменной =35.

Итак, вся транспортная матрица заполнена. Балансы мощности по строкам (по узлам источников) и по столбцам (по узлам потребителей) выполняются. Все переменные неотрицательны. Полученное исходное решение является допустимым. В этом решении:

свободные переменные: =0, =0, =0, =0.

базисные переменные: =15, =20, =15, =10, =30, =15 =10, =35. Значение целевой функции:

Z = + + + + + + + + +

+ + + .

Z = 15·1+0·2+20·3+15·5+0·4+10·1+30·1+0·2+15·1+10·2+0·5+35·10=575 у.е.

.

(40) (60)

(50)

15

35

15 15 10 10 20 30

(50)

(30) (20) (50)

Рис. 4.5. Схема электрической сети, полученному допустимому решению.

Из полученного нами результата допустимого решения задачи, можно сделать следующие выводы: значение целевой функции возросло по сравнению с допустимым решением варианта №3, но при этом все четыре потребителя , , и имеют дополнительный источник питания.

Поиск по сайту: