Решение. Запишем
отдельно матрицу стоимостей для того, чтобы удобнее было выбирать стоимости,
вычеркивать строки и столбцы:
1 4 6 3
среди элементов
матрицы стоимостей выбираем наименьшую стоимость . Это стоимость перевозки груза от первого
поставщика первому потребителю. В соответствующую клетку (1,1) записываем
максимально возможную перевозку (табл 4). Запасы первого поставщика уменьшаем
на 80, .
Исключаем из рассмотрения первого потребителя, так как его запросы
удовлетворены. В матрице С вычеркиваем первый столбец.
Таблица 4
80
120
160
120
120
1
80
3
4
2
40
160
4
5
8
80
3
80
200
2
3
120
6
80
7
В оставшейся
матрицы С наименьшей является стоимость , максимально возможная перевозка, которую
можно осуществить от первого поставщика к четвертому потребителю, равна . В соответствующую летку
таблицы записываем перевозку . Запасы первого поставщика исчерпаны,
исключаем его из рассмотрения. В матрице С вычеркиваем первую строку. Запросы
четвертого потребителя уменьшаем на 40
В оставшейся
части матрицы С минимальная стоимость . Заполняем одну из двух клеток таблицы (2,4)
или (3,2). Пусть в клетку (2,4) запишем . Запросы четвертого потребителя удовлетворены
полностью, исключаем его из рассмотрения, вычеркиваем четвертый столбец в
матрице С. Уменьшаем запасы второго поставщика
В оставшейся
части матрицы С минимальная стоимость . Запишем в клетку таблицы (3,2) перевозку Исключаем из рассмотрения
второго потребителя, а из матрицы С второй столбец. Вычисляем
В оставшейся
части матрицы С наименьшая стоимость Запишем в клетку таблицы (3,3) перевозку Исключаем из рассмотрения
третьего поставщика, а из матрицы С третью строку. Определяем .
В матрице С
остался единственный элемент . Записываем в клетку таблицы (2,3) перевозку .
Проверяем
правильность построения опорного решения. Число занятых клеток таблицы равно N=m+n-1=3+4-1=6. Применяя метод
вычеркивания, проверяем линейную независимость векторов условий,
соответствующих положительным координатам решения. Порядок вычеркивания показан
на матрице Х:
1 2 5 6
Решение является
«вычеркиваемым» и, следовательно, опорным.
Переход от
опорного решения к другому. В транспортной задаче переход от оного опорного
решения к другому осуществляется с помощью цикла. Для некоторой свободной
клетки таблицы строится цикл, содержащий часть клеток, занятых опорным
решением. По этому циклу перераспределяются объемы перевозок(осуществляется
сдвиг по циклу). Перевозка «загружается» в выбранную свободную клетку и
освобождается одна из занятых клеток, получается новое опорное решение.
Если таблица
транспортной задачи содержит опорное решение, то для любой свободной клетки
таблицы существует единственный цикл, содержащий эту клетку и часть клеток,
занятых опорным решением.
Для удобства вычислений
вершины циклов нумеруют и отмечают нечетные знаком «+», а четные знаком «-».
Такой цикл называется означенным.
Сдвигом по циклу
на величину называется
увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком
«+», и уменьшение объемов перевозок на ту же величину во всех не четных клетках,
отмеченных знаком «-».
1.2.3 МЕТОД ПОТЕНЦИАЛОВ
Широко
распространенным методом решения транспортных задач является метод потенциалов.
Если допустимое
решение , i=1,2,…,m; j=1,2,…n транспортной задачи является
оптимальным, то существуют потенциалы (числа) поставщиков i=1,2,…,m и потребителей j=1,2,…,n, удовлетворяющее следующим образом:
Группа равенств
(2.1) используется как система уравнений для нахождения потенциалов. Данная
система уравнений имеет m+n неизвестных i=1,2,…,m и j=1,2,…,n. Число уравнений системы,
как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Так как число неизвестных системы на единицу больше числа уравнений, то
одной из них можно задать значение произвольно, а остальные найти из системы.
Группа неравенств
(2.2) используется для проверки оптимальности опорного решения. Эти неравенства
удобнее представить в следующем виде:
(2.3)
Числа называются оценками для
свободных клеток таблицы (векторов условий) транспортной задачи.