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

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

Справа указаны заданные мощности источников А₁ и А₂, снизу - заданные мощности потребителей В₁, В₂, В₃ справа внизу-значение целевой функции Z. Непосредственно в клетках транспортной матрицы записаны подлежащие определению искомые переменные х_ij и заданные значения удельных стоимостей передачи мощности z _ij.

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

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

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

2. В выбранную клетку в качестве базисной переменной заносится наименьшая из двух величин A_i или B_j, т.е. х_ij=miп(А_iВ_j).

При этом выполняется баланс мощности по строке i или столбцу j, в которые входит переменная х_ij.

3.В остальные клетки строки i или столбца j, для которых выполнен баланс мощности, заносятся нули, соответствующие свободным переменным. Большая из двух величин A_i и B_j условно заменяется разностью этих двух величин.

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

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

Пример 4. Найти допустимое решение для задачи примера 3 при следующих исходных данных:

Решение. Изобразим транспортную матрицу размерностью 2x3 (табл. 3.2) и будем заполнять ее в соответствии с алгоритмом минимальной удельной стоимости.

В транспортной матрице выбирается клетка с минимальным значением z _ij. Это клетка с переменной х₁₁ и удельной стоимостью z ₁₁=1,2.

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

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

Из оставшихся незаполненных клеток транспортной матрицы выбирается клетка с наименьшей удельной стоимостью z₁₃=l,5. В качестве базисной переменной в эту клетку заносится меньшее из двух значений мощностей х₁₃=min(A₁=30, B₃=35)=30. Баланс для 1-й строки (1-го источника) выполнен. В остальные клетки этой строки заносим нули (свободная переменная x₁₂=0).

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

Из оставшихся незаполненных клеток транспортной матрицы выбираем клетку с наименьшей удельной стоимостью z₂₃=2,1. В качестве базисной переменной в эту клетку заносим меньшее из двух значений мощностей х₂₃ = min(A₂=30, B₃=5)=5. Баланс для 3-го столбца (3-го потребителя) выполнен.

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

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

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

свободные переменные: х₁₂=0, х₂₁=0;

базисные переменные: х₁₁=20, х₁₃=30, х₂₂=25, х₂₃=5 е.м.;

значение целевой функции