Нахождение допустимого решения

Исходное допустимое решение может быть получено по алгоритму минимальной удельной стоимости.

1. В транспортной матрице в строках, соответствующих источникам, выбирается клетка с минимальным значением . Если имеется несколько таких клеток, то выбирается любая из них.

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

3. В остальные клетки строки или столбца , для которых выполнен баланс мощности, заносятся нули, соответствующие свободным переменным.

4. Большая из двух величин и условно заменяется разностью этих двух величин.

5. Из оставшихся незаполненных клеток транспортной матрицы вновь выбирается клетка с минимальным значением . Далее пункты 2 и 3 повторяются до полного заполнения всех клеток транспортной матрицы.

Общее количество переменных составляет . Количество отличных от нуля базисных переменных составляет (n+m-1) . Количество равных нулю свободных переменных составляет .

Найдем исходное допустимое решение и заполним транспортную матрицу (таблица 2.1).

В таблице 1.1 выбираем минимальное значение .

В качестве базисной переменной заносим .

При этом выполняется баланс мощности по столбцу 6.

В остальные клетки столбца 6 заносим нули, соответствующие свободным переменным.

Большую из величин условно заменяем разностью этих величин .

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

Транспортная матрица со значениями мощностей, соответствующая допустимому решению, представлена в таблице 2.1.

Таблица 2.1 – Транспортная матрица, соответствующая допустимому решению

			4,4		1,9

Во всех узлах должны выполняться балансы мощности

. (2.1)

;

;

;

.

Транзитные мощности через узлы должны быть равны нулю

. (2.2)

S₁₁=0; S₂₂=0; S₃₃=0; S₄₄=0; S₅₅=0; S₆₆=0; S₇₇=0.

Значение целевой функции, определяемое по выражению (1.1), составляет

_.

Значение заносится в правый нижний угол транспортной матрицы (таблица 2.1).

На основании данных таблицы 2.1 строим схему соединений источников электроэнергии и потребителей, соответствующую допустимому решению.

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