Решение транспортных задач венгерским методом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
nbsp;
Исходя из условия задачи, требуется определить минимальные транспортные затраты на перевозку груза с некоего предприятия на оптовый склад. Поэтому в качестве переменной следует взять элемент плана Хij, который является количеством груза (в килограммах) транспортированного с некоего предприятия на оптовый склад.
.2 Целевая функция
Так как стоимость (Сij) перевозки одного килограмма груза известна, то общие затраты на его перевозку составляют: Сij*Хij. Обозначив суммарные затраты через L, можно дать следующую математическую формулировку целевой функции: определить такие значения Хij, при которых значение L было бы минимальным.
.3 Ограничения
При распределении груза по пунктам потребления следует учесть, что суммарное количество груза, хранящегося на предприятии, должно быть равно суммарному количеству груза, требуемого складами.
Все вышеперечисленное приводит к построению линейной модели вида:
5 ПОЛУЧЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ
.1 Решение варианта № 24 вручную
Условие представлено в таблице 5.1.
Таблица 5.1 - Исходные данные к расчету варианта № 24
AiС:12147.231001512.43.15507.718221200231917.11850Bj210040805206700
Проверка условия баланса:
Так как условие баланса выполняется, то в матрицу С нечего не добавляется.
5.1.1 Предварительный этап
Находим в каждом столбце матрицы С минимальный элемент, вычетаем его из всех элементов столбца. Получаем матрицу С.
В каждой строке матрицы С отыскиваем минимальный элемент, который вычитается из всех элементов строки. В результате получем матрицу С0. Матрица С0 имеет вид:
С0:2.702.57.30005.618.98.707.4В соответствии с матрицей С0 строим план Х0:
AiХ0:310005500120004301420Bj9000520
Построив начальный план Х0, рассчитаем невязки по столбцам и по строкам.
по столбцам:
b1=2100-1200=900;
b2=4800-980-430=0;
b3=520-0=520;
по строкам:
а1=3100-3100=0;
а2=550-550=0;
а3=1200-1200=0;
а4=1850-430=1420;
Рассчитаем суммарную невязку плана
т.к то переходим к первой итерации.
.1.2 Первая итерация
Этап разметки
Символами + выделяем столбы с нулевыми невязками. Символами - отметим существенные нули матрицы .
+2.72.5C0:7.305.618.98.77.4
Этап поиска
В невыделенной части матрицы С0 найденные нули отмечаем штрихом. Анализируем невязку такого нуля по строке: a=0 . Если невязка нулевая, то отмечаем строку +. Просматриваем выделенную строку, если в ней стоит существенный ноль, находящийся в выделенном столбце, то такой ноль отмечаем *, а выделение с этого столбца снимаем: (+). Продолжаем данную процедуру до тех пор, пока не будет найден ноль в строке с положительной невязкой - в данном случае это ноль в строке 4. Теперь переходим к этапу построения цепочки.
(+)2.72.5+C0:7.3*0'+'5.618.9+8.7'7.4
Этап построения цепочки
Цепочка венгерского метода состоит из нечетного числа элементов, начинается нулем в строке с положительной невязкой, проходит по столбцу до нуля, отмеченного знаком *, и заканчивается нулем, находящемся в столбце с положительной невязкой. Полученная цепочка показана в таблице:
Этап коррекции плана Х
Этот этап начинается сразу после построения цепочки. Для коррекции плана находим корректирующий элемент . Находим его по минимуму из невязки строки начала цепочки, из невязки столбца конца цепочки и значения элемента Xij, соответствующего 0*. =min{1420, 520, 550}=520.
(+)2.7'2.5+C0:7.3*0'+'5.618.9+8.7'7.4
Прибавляем =520 к элементам Xij, которым в цепочке соответствовали элементы Сij=0, и отнимаем =520 от элементов Xij, которым в цепочке соответсвовали элементы Cij=0*:
AiХ1:3100030520012000950900Bj90000
Теперь рассчитаем невязки по столбцам и по строкам.
по столбцам:
b1=2100-1200=900;
b2=4800-3100-30-950=0;
b3=520-520=0;
по строкам:
а1=3100-3100=0;
а2=550-30-520=0;
а3=1200-1200=0;
а4=1850-1850=0;
Рассчитаем суммарную невязку плана Х1:т.к. то переходим ко второй итерации.
.1.3 Вторая итерация
Этап разметки
Символами + выделяем столбы с нулевыми невязками. Символами - отметим существенные нули матрицы .
++2.72.5C0:7.30'5.618.9+8.77.4
Видно, что нули в невыделенной части матрицы С0 закончились, поиск продолжать нельзя, следовтельно необходимо выполнить эквивалентные преобразвания матрицы С0.
Этап эквивалентных преобразований
На данном этапе находится минимальный положительный элемент в невыделенной части матрицы С0 h=min{2.7, 7.3, 8.7}=2.7; h прибавляется к выделенным столбцам и вычитается из невыделенных строк. Получили матрицу С1:
002.5C14.60008.321.6607.4
Этап разметки
Символами + выделяем столбы с нулевыми невязками. Символами - отметим существенные нули матрицы .
++2.5C14.68.321.667.4
Этап поиска
В невыделенной части матрицы С1найденные нули отмечаем штрихом. Анализируем невязку такого нуля по строке: a=0 . Если невязка нулевая, то отмечаем строку +. Просматриваем выделенную строку, если в ней стоит существенный ноль, находящийся в выделенном столбце, то такой ноль отмечаем *, а выделение с этого столбца снимаем: (+). Продолжаем данную процедуру до тех пор, пока не будет найден ноль в строке с положительной невязкой - в данном случае это ноль в строке 4. Теперь переходим к этапу построения цепочки.
(+)(+)'*2.5+C14.6'*+'8.321.6+6'7.4
Этап построения цепочки
Цепочка венгерского метода состоит из нечетного числа элементов, начинается нулем в строке с положительной невязкой, проходит по столбцу до нуля, отмеченного знаком *, и заканчивается нулем, находящемся