Транспортная задача линейного программирования — КиберПедия 

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

Транспортная задача линейного программирования

2017-10-16 453
Транспортная задача линейного программирования 0.00 из 5.00 0 оценок
Заказать работу

Транспортная задача линейного программирования имеет следующую формулировку.

Имеется некоторый однородный продукт, сосредоточенный у m поставщиков Ai в количестве ai (i=1, 2, …,m) единиц соответственно, необходимо доставить n потребителям Bj в количестве bj(j=1, 2, …,n) единиц. Известна стоимость Cij перевозки единицы груза от i–го поставщика к j–му потребителю. Необходимо составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость.

Математическую модель этой задачи можно представить в следующем виде.

Найти наименьшее значение линейной функции

при ограничениях

Обозначим через xij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю; тогда условие задачи можно записать в виде таблицы 1.5, которую в дальнейшем будем называть матрицей планирования.

Таблица 1.5.

 

Поставщики Потребители   Запасы
  B1   B2   …   Bn
А1 C11 X11 C12 X12 …. C1n X1n a1
А2 C21 X21 C22 X22 C2n X2n a2
--- --- --- --- --- ---
Аm Cm1 Xm1 Cm2 Xm2 Cmn Xmn am
Потребности   b1   b2   …   bn =

 

Составим математическую модель задачи. Т.к. от i-го поставщика к j-му потребителю запланировано к перевозке xij единиц груза, то стоимость перевозки составит CijXij. Стоимость всего плана выразим двойной суммой:

Сумму ограничений получаем из следующих условий задачи:

а) все грузы должны быть вывезены, т.е. (из строк таблицы);

б) все потребности должны быть удовлетворены, т.е. (уравнения получаются из столбцов таблицы 6);

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

Найти наименьшее значение линейной функции

(1.34)

при ограничениях

(1.35)
(1.36)
(1.37)

В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е. . Такая модель называется закрытой.

Теорема. Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.

Алгоритм метода потенциалов.

1. Проверяем условие разрешимости транспортной задачи, т.е.

(1.38)

Если это условие не выполняется, возможны два случая:

а) ,вводим фиктивного потребителя ВФ n+1, с потребностями bФ= .

б) , вводим фиктивного поставщика АФ m+1, c ресурсами аф= .

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

2. Строим первоначальный опорный план. Существует ряд методов для его построения: метод «северо-западного угла», метод «наилучший элемент матрицы», метод «наилучший элемент строки», «аппроксимация» и др.

Рассмотрим метод наилучшего элемента матрицы:

a) среди всех стоимостей выбираем наилучший элемент (если задача была поставлена на минимум, тогда выбирается наименьший, а если задача была поставлена на максимум, тогда наибольший элемент);

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

в) переходим к шагу а). Процесс продолжается до тех пор, пока все ресурсы не будут распределены и весь спрос не будет удовлетворен.

Замечание 1: если при распределении поставок, одновременно вычеркивается строка и столбец, то получим вырожденный план.

Поэтому в одну из свободных клеток (не относящихся к фиктивным), с наилучшим Cij в одновременно вычеркиваемых строке и столбце ставим нуль поставку, т.е. увеличиваем число занятых клеток до (m+n-1).

3. Проверяем условие невырожденности плана: количество заполненных клеток должно быть равно m+n-1. Если план вырожденный – устраняем вырождение (замечания 1 и 2).

4. Подсчитываем значение линейной формы L(Х).

5. Проверяем условие оптимальности плана:

a) для всех занятых клеток (т.е. Xij>0) строим систему уравнений с (m+n) неизвестными Ui(i=1,m и Vj(j=1,n).

-Ui+Vj=Cij.

Так как эта система является неопределенной, то можно одной переменной задать произвольное значение. Для простоты расчета полагаем вычисления предположим U1=0. Полученные Ui и Vj вводим в дополнительные столбец и строку;

б) для всех свободных клеток (т.е. Xij=0) производим оценку по формуле

Если все при решении задачи на минимум (все при решении задачи на максимум), тогда полученный план будет оптимальным.

Выписываем план перевозок X=(Xij) и значение L(X).

Если имеется хотя бы одна оценка при решении задачи на минимум ( при решении задачи на максимум), то план не оптимальный, и переходим к следующему шагу.

6. Среди всех положительных оценок (задача на минимум) выбираем наибольшую. При решении задачи на максимум, из всех отрицательных оценок выбираем наибольшую по абсолютному значению. Обозначим выбранную оценку через .

7. Для клетки с выбранной оценкой строим прямоугольный контур, состоящий горизонтальных и вертикальных отрезков, которые пересекаются под прямым углом. Одна вершина контура должна находиться в свободной клетке с номером (), а все остальные в занятых клетках.

8. Начиная с () вершинам контура присваиваем знаки «плюс» и «минус».

9. Среди вершин контура со знаком «минус» выбираем наименьшее значение и обозначим ее q.

10. Передвигаем величину q по контуру, прибавляя ее к поставкам, находящимся в вершинах со знаком «плюс», и вычитаем из поставок, стоящих в вершинах, имеющих знак «минус».

Получаем новый опорный план. Возвращаемся к шагу 3.

Замечание 2: Если в вершинах контура со знаком «минус» имеется две (или несколько) одинаковых наименьших поставок q, то при перераспределении поставок по контуру (чтобы избежать вырожденности плана) необходимо в одну или несколько из этих вершин записать нуль–поставку (предпочтение отдается той вершине которая соответствует клетке с наилучшим ).

Замечание 3: Подсчитав значение линейной формы для первоначального опорного плана по формуле:

последующие значения L(X) можно вычислять по формуле

,

где «плюс» (если задача решается на максимум), и «минус» (если задача решается на минимум).

Замечание 4: Если при полученном оптимальном плане имеются нулевые оценки свободных клеток, то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой нужно построить контур и сделать перераспределение поставок, вновь полученный план также будет являться оптимальным. Тогда по основной теореме ЛП любой план будет оптимальным.

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

a1=4, a2=8, a3=8; b1=7, b2=3, b3=6, b4=6.

1. Проверяем условие разрешимости:

; .

Вводим фиктивного поставщика Аф с ресурсами aф=22-20=2.

2. Строим первоначальный опорный план методом наилучшего элемента матрицы (таблица 1.6.). Наименьшая стоимость С41=0, направляем в клетку (4,1) поставку x41=min(2,7)=2. Все ресурсы Аф исчерпаны, поэтому эту строку зачеркиваем. Из оставшихся стоимостей наименьшая С14=1, тогда x14=min(8,4)=4 и т.д. Процесс продолжается до полного распределения ресурсов. Получим следующий план

3. Полученный план невырожденный, т.к. m+n-1=7 и число занятых клеток в таблице 1.6. равно 7.

4. .

5. Проверяем условие оптимального плана. Для занятых клеток строим систему :

(1,4): ;

(2,2): ;

(2,3): ;

(3,1): ;

(3,2): ;

(3,4): ;

(4,1): .

Полагаем находим все значения:

.

Заполняем в таблице 1.6. столбец и строку . Находим оценки свободных клеток,

 

6. План Х1 –неоптимальный, т.к. имеются положительные оценки свободных клеток. Выбираем из них наибольшую .

7. Для клетки с номером (2,4) строим контур. Вершины контура: (2,4), (3,4), (3,2), (2,2).

8. Расставляем знаки по вершинам начиная с (2,4).

9. Среди поставок стоящих в клетках (2,2) и (3,4), выбираем наименьшую: .

10. Перемещаем по контуру, прибавляя ее к поставкам в клетках (2,4) и (3,2), и отнимая от поставок в клетках (2,2) и (3,4).

Получим новые поставки: 3 – в клетке (3,2), 2 - в клетке (2,4), а клетки (2, 2) и (3,4) становятся свободными. Имеем случай вырождения (Замечание 2). В клетку с номером (2,2) (т.к.С2234) вставим нуль поставку. Новый опорный план записываем в таблицу 1.7., переходим к шагу 3.

3. Новый план,

4. .

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

Для занятых клеток:

(1,4): ;

(2,4): ;

(2,3): ;

(2,2): ;

(3,1): ;

(3,2): ;

(4,1): .

Отсюда:

.

Для свободных клеток:

 

Следовательно, план Х2 оптимальный. Выписываем его (поставка по дополнительной строке не заносится) и значение линейной формы.

, .

Так как , то задача имеет множество оптимальных планов. Для клетки (2,1) можно построить контур и сделать перераспределение поставок. Получим Х3, который так же является оптимальным и . Тогда по основной теореме ЛП любой план , где , является также оптимальным планом задачи [3].

Таблица 1.6

Вj Ai     B1   B2   B3   B4 Ресурсы
  Vj Ui V1=-1 V2=-2 V3=-3 V4=1  
А1 U1=0          
А2 U2=-5   - 3   + 3    
A3 U3=-5   + 3   - 6  
А4 U4=-1          
Потребности           20+2

 

Таблица 1.7

Вj Ai     B1   B2   B3   B4   Ресурсы
  Vj Ui V1=2 V2=1 V3=0 V4=1  
А1 U1=0          
А2 U2=-2          
A3 U3=-2          
А4 U4=2          
Потребности            

 

 

 


Поделиться с друзьями:

Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьше­ния длины пробега и улучшения маневрирования ВС при...

Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...

Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...

Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.009 с.