Применение методов линейного программирования для оптимизации стоимости перевозок

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Реферат по дисциплине: Методы и модели в экономике и менеджменте.

на тему: «Применение методов линейного программирования для оптимизации стоимости перевозок»

Воронеж 2010

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

Обозначим количество груза, имеющегося на каждой из баз (запасы), соответственно, а общее количество имеющегося в наличии груза-:

;

заказы каждого из потребителей (потребности) обозначим соответственно, а общее количество потребностей — :

Тогда при условии

мы имеем закрытую модель, а при условии

— открытую модель транспортной задачи.

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

Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется «перевалочный пункт», например — склад.

План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок (Таблица 3.):

Таблица 3. — План перевозок с указанием запасов и потребностей

Условие или означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное означает количество груза, перевозимого с базы потребителю: совокупность этих величин образует матрицу (матрицу перевозок).

Очевидно, переменные должны удовлетворять условиям:

Система (3.) содержит уравнений с неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (3.) могут быть разделены на две группы: первая группа из т первых уравнений («горизонтальные» уравнения) и вторая группа из п остальных уравнений («вертикальные» уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (3.) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.

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

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

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

В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные с помощью вертикальных уравнений, мы получаем уравнение или короче где символ означает сумму всех свободных неизвестных. Аналогично, исключив из первого вертикального уравнения базисные неизвестные с помощью горизонтальных уравнений, мы получаем уравнение Так как для закрытой модели транспортной задачи, то полученные нами уравнения (3.) и (3.) одинаковы и, исключив из одного из них неизвестное, мы получим уравнение-тождество 0=0, которое из системы вычеркивается.

Итак, преобразование системы (3.) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (3.). Остальные уравнения остаются неизменными. Система приняла вид

В системе (3.) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного [она входит в первое уравнение системы (3.)]. В системе (3.) имеется уравнений, выделенный базис содержит неизвестных, а, следовательно, и ранг системы (3.) .

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

Совокупность тарифов также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу 3.:

Таблица 3. — Совокупность тарифов данные о запасах и потребностях

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

Требуется в области допустимых решений системы уравнений (3.) и (3.) найти решение, минимизирующее линейную функцию (3.).

Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен то среди всех неизвестных выделяется базисных неизвестных, а остальные · неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и · пустых клеток.

На предприятии ОАО «Электросигнал» имеется 4 транзитных склада А_i, на которых хранятся сборочные узлы и 5 цехов B_j, занимающихся сборкой готовой продукции. Ниже, в таблице 3., приведены данные по количеству сборочных узлов на каждом складе, запросы цехов и стоимость перевозки одного агрегата из А_i в B_j. Необходимо составить такой план перевозок, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок.

Таблица 3. — Исходные данные по количеству сборочных узлов и стоимость перевозки

В данном случае Уa_i=225 >Уb_j=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного цеха B₆ с потребностью b₅=225−220=5 и стоимостью перевозок с_i6=0.Имеем таблицу 3. :

Таблица 3. ;

Математическая модель: обозначим x_ij — количество товара, перевозимого из А_i в B_j. Тогда

x₁₁ x₁₂ x₁₃ x₁₄ x₁₅ x₁₆

x₂₁ x₂₂ x₂₃ x₂₄ x₂₅ x₂₆

X = x₃₁ x₃₂ x₃₃ x₃₄ x₃₅ x₃₆ — матрица перевозок.

x₄₁ x₄₂ x₄₃ x₄₄ x₄₅ x₄₆

min (x₁₁+2x₁₂+3x₁₃+2,5x₁₄+3,5x₁₅+0,4x₂₁+3x₂₂+x₂₃+2x₂₄+3x₂₅+0,7x₃₁+x₃₂+x₃₃+0,8x₃₄+1,5x₃₅++1,2x₄₁+2x₄₂+2x₄₃+1,5x₄₄+2,5x₄₅) (3.)

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅+x₁₆=50

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅+x₂₆=20

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅+x₃₆=75

x₄₁+x₄₂+x₄₃+x₄₄+x₄₅+x₄₆=80

x₁₁+x₂₁+x₃₁+x₄₁=40

x₁₂+x₂₂+x₃₂+x₄₂=50

x₁₃+x₂₃+x₃₃+x₄₃=15

x₁₄+x₂₄+x₃₄+x₄₄=75

x₁₅+x₂₅+x₃₅+x₄₅=40

x₁₆+x₂₆+x₃₆+x₄₆=5

x_ij?0 (i=1,2,3,4; j=1,2,3,4,5,6) (3.)

Двойственная ЗЛП:

max (50u₁+20u₂+75u₃+80u₄+40v₁+50v₂+15v₃+75v₄+40v₅+5v₆) (3.)

u₁+v₁?1

u₁+v₂?2

u₁+v₃?3 (3.)

u₁+v₄?2,5

u₁+v₅?3,5

u₁+v₆?0

u_i, v_j — произвольные (i=1,2,3,4; j=1,2,3,4,5,6)

Будем искать первоначальный план по методу наименьшей стоимости:

1) x₂₁=20 и 2-ую строку исключаем;

2) x₃₁=20 и 1-ый столбец исключаем;

3) x₃₄=55 и 3-ю строку исключаем;

4) x₄₄=20 и 4-ый столбец исключаем;

5) x₁₂=50 и 1-ю строку и 2-ой столбец исключаем и x₃₂=0;

6) x₄₃=150 и 3-ий столбец исключаем;

7) x₄₅=40 и 5-ый столбец исключаем и x₄₆=5.

Составим таблицу 3.. Здесь и далее в нижнем правом углу записываем значение перевозки.

Таблица 3. — Проведение итераций

Стоимость 1-ого плана:

D₁=2*50+0,4*20+0,7*20+0,8*55+2*15+1,5*20+2,5*40=326.

Будем улучшать этот план методом потенциалов: u_i— потенциал А_i, v_j— потенциал B_j. Тогда u₁+v₂=2,u₂+v₁=0,4, u₃+v₁=0,7, u₃+v₂=1, u₃+v₄=0,8, u₄+v₃=2, u₄+v₄=1,5, u₄+v₅=2,5, u₄+v₆=0.Положим u₁=0,тогда v₂=2,u₃=-1,v₁=1,7,v₄=1,8, u₂=-1,3,u₄=-0,3, v₃=2,3,v₅=2,8,v₆=0,3.Составим таблицу 3. :

Таблица 3. — Проведение итераций

В верхнем левом углу здесь и далее записываем значение u_i+v_j-c_ij. Имеем: u₁+v₁—c₁₁ =0,7>0, u₁+v₆-c₁₆ =0,3>0, u₃+v₃-c₃₃ =0,3>0, u₃+v₅-c₃₅ =0,3>0,

u₄+v₁-c₄₁ =0,2>0. => По критерию оптимальности, первый план не оптимален. Далее max (0,7;0,3;0,3;0,3;0,2)=0,7. => Поместим перевозку в клетку А₁В₁, сместив 20=min (20,50) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u₁+v₁=1,u₁+v₂=2,u₂+v₁=0,4,u₃+v₂=1, u₃+v₄=0,8, u₄+v₃=2, u₄+v₄=1,5, u₄+v₅=2,5, u₄+v₆=0. Положим u₁=0,тогда v₁=1,u₂=-0,6,v₂=2,v₄=1,8, u₃=-1, u₄=-0,3,v₃=2,3,v₅=2,8,v₆=0,3. Составим таблицу 3. :

Таблица 3. — Проведение итераций

Стоимость 2-ого плана:

D₂=1*20+2*30+0,4*20+1*20+0,8*55+2*15+1,5*20+2,5*40=312.

Имеем:u₁+v₆-c₁₆ =0,3>0, u₂+v₃-c₂₃ =0,7>0, u₃+v₃-c₃₃ =0,3>0, u₃+v₅-c₃₅ =0,3>0. => По критерию оптимальности, второй план не оптимален. Далее max (0,3;0,7;0,3;0,3)=0,7 => Поместим перевозку в клетку А₂В₃, сместив 15=min (20,30,55,15) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u₁+v₁=1,u₁+v₂=2,u₂+v₁=0,4,u₃+v₂=1, u₃+v₄=0,8, u₂+v₃=1, u₄+v₄=1,5, u₄+v₅=2,5, u₄+v₆=0. Положим u₁=0,тогда v₁=1,u₂=-0,6,v₂=2,v₄=1,8, u₃=-1, u₄=-0,3,v₃=1,6, v₅=2,8, v₆=0,3. Составим таблицу 3.:

Таблица 3. — Проведение итераций

Стоимость 3-его плана:

D₃=1*35+2*15+0,4*5+1*15+0,8*40+1*35+1,5*35+2,5*40=301,5.

Имеем:u₁+v₆-c₁₆ =0,3>0,u₃+v₅-c₃₅ =0,3>0. => По критерию оптимальности, третий план не оптимален. Далее max (0,3;0,3)=0,3. => Поместим перевозку в клетку А₃В₅, сместив 40=min (40,40) по циклу, указанному в таблице штрихом. Получим новую таблицу. Чтобы 4-ый план был невырожденным, оставим в клетке А₄В₅ нулевую перевозку. Найдем потенциалы: u₁+v₁=1,u₁+v₂=2,u₂+v₁=0,4,u₃+v₂=1, u₄+v₅=2,5, u₂+v₃=1, u₄+v₄=1,5, u₃+v₅=1,5, u₄+v₆=0. Положим u₁=0,тогда v₁=1,u₂=-0,6,v₂=2,v₄=1,5, u₃=-1,u₄=0, v₃=1,6, v₅=2,5, v₆=0. Составим таблицу 3. :

Таблица 3. — Проведение итераций

Стоимость 4-ого плана:

D₄=1*35+2*15+0,4*5+1*15+1*35+1,5*40+1,5*75=289,5.

Для всех клеток последней таблицы выполнены условия оптимальности:

1) u_i+v_j-с_ij=0 для клеток, занятых перевозками;

2) u_i+v_j-с_ij ?0 для свободных клеток.

Несодержательные ответы:

Прямой ЗЛП:

35 15 0 0 0 0

5 0 15 0 0 0

X = 0 35 0 0 40 0

0 0 0 75 0 5

min=289,5.

Двойственной ЗЛП:

U₁=0; U₂=-0,6; U₃=-1; U₄=0; V₁=1; V₂=2; V₃=1,6; V₄=1,5; V₅=2,5; V₆=0.

max=289,5.

Так как min=max, то по критерию оптимальности найдены оптимальные решения прямой и двойственной ЗЛП. Содержательный ответ: Оптимально перевозить так:

Из А₁ в B₁ — 35 сборочных агрегатов;

Из А₁ в B₂ — 15 сборочных агрегатов;

Из А₂ в B₁ — 5 сборочных агрегатов;

Из А₂ в B₃ — 15 сборочных агрегатов;

Из А₃ в B₂ — 35 сборочных агрегатов;

Из А₃ в B₅ — 40 сборочных агрегатов;

Из А₄ в B₄ — 75 сборочных агрегатов.

При этом стоимость минимальна и составит D_min=289,5. 5 сборочных агрегатов необходимо оставить на складе А₄ для их последующей перевозки в другие Цеха.

1. Е. Г. Гольштейн, Д. Б. Юдин «Задачи линейного программирования транспортного типа», Москва, 2007.

2. И. Л. Акулич, В. Ф. Стрельчонок «Математические методы и компьютерные технологии решения оптимизационных задач», Рига, 2006.

3. Астафуров В. Г., Колодникова Н. — Компьютерное учебное пособие, раздел «Анализ на чувствительность с помощью двойственной задачи», Томск-2004.

4. Алесинская Т. В. — Задачи по исследованию операций с решениями. Москва, 2008.

5. Смородинский С. С., Батин Н. В. — Оптимизация решений на основе методов и моделей математического программирования: Учебное пособие. Воронеж, 2009