Планирование транспортирования грузов (транспортная задача линейного программирования)

Задание №5

Вариант №4

Планирование транспортирования грузов (транспортная задача линейного программирования)

Исходные данные:

Первоначальное закрепление потребителей за постовщиками.

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

Первоначальное закрепление потребителей за постовщиками.

После распределения груза рассчитываем транспортную работу при данном распределении:

Для уменьшения транспортной работы рассмотрим возможность перемещения загрузки в клетки с меньшим расстоянием.

Рассмотрим возможность передвижки загрузки в строке Б3 (таблица №3). Из (А4Б3) загрузку переместить в (А1Б3) это перемещение компенсируем передвижкой загрузки (А1Б2) в (А4Б2).(показано стрелками) При этом, сумма расстояний, от куда происходит перемещение 14+7=21 больше куда происходит перемещение 9+11=20. Следовательно данное перемещение целесообразно. Кол-во передвигаемого груза не более 20 т.(результат передвижки в таблице №3а)

Также сделаем еще пару передвижек. Из (А3Б1) в (А2Б1) с заменой (А2Б4) в (А3Б4). Сумма перемещений из 14+15=29 в 16+12=28. Кол-во груза 10 т. (результат передвижки в таблице №3б)

Также делаем еще передвижку. Из (А2Б1) в (А1Б1) с заменой (А1Б3) в (А2Б3). Сумма перемещений из 12+9=21 в 8+11=19. Кол-во груза 10 т. (результат передвижки в таблице №4)

Аналогично рассмотрим возможность улучшения распределения по столбцам.

В данном примере улучшения по столбцам мною не найдены. Рассчитаем транспортную работу при данном распределении.

Что на меньше, чем при первоначальном закреплении.

Проверка оптимальности распределения.

Для проверки распределения находим потенциалы -столбцов, -строк. Один из столбцов принимаем за 0. Этот столбец должен иметь наибольшее расстояние в загруженной клетке. В нашем случае это клетка А3Б5, потенциал . Связь потенциалов рассчитываем через связь

По загруженным клеткам определяем потенциал строк Б4 и Б5

По загруженной клетке А2Б4 определяем потенциал столбца А2

По загруженной клетке А2Б3 определяем потенциал строки Б3

По загруженной клетке А1Б3 определяем потенциал столбца А1

По загруженной клетке А1Б1 и А1Б2 определяем потенциал строк Б1 и Б2.

По загруженной клетке А4Б2 определяем потенциал столбца А4

Численное значение всех потенциалов определено так как соблюдено условие матрицы

где n-число основных строк; m-число основных столбцов

число загруженных клеток равно условию 8=5+4-1

После однозначного определения потенциалов рассматриваются все не загруженные клетки и среди них отыскиваем положительное число.

Незагруженных клеток с положительными значениями нет.

Значит полученное распределение улучшить нельзя, т.е. оно оптимально.

Дата добавления: 2015-09-30