Контрольная работа Применение методов линейного программирования для оптимизации стоимости перевозок
Работа добавлена на сайт bukvasha.net: 2015-10-25Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Реферат
по дисциплине: Методы и модели в экономике и менеджменте.
на тему: «Применение методов линейного программирования для оптимизации стоимости перевозок»
Воронеж 2010
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с
Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
|
|
(3. )
Тогда при условии
| (3. ) |
|
– открытую модель транспортной задачи.
Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза
Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.
План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок (Таблица 3. ):
Таблица 3. - План перевозок с указанием запасов и потребностей
| Пункты Отправления | Пункты назначения | Запасы | |||
| | | … | | ||
| | | | … | | |
| | | | … | | |
| … | … | … | … | … | … |
| | | | … | | |
| Потребности | | | … | | или |
Условие
Очевидно, переменные
|
Система (3. ) содержит
Такая структура системы (3. ) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием
|
где символы
При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь
В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные
или короче
|
где символ
|
Так как для закрытой модели транспортной задачи
Итак, преобразование системы (3. ) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (3. ). Остальные уравнения остаются неизменными. Система приняла вид
|
В системе (3. ) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного
Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы
Совокупность тарифов
Таблица 3. - Совокупность тарифов данные о запасах и потребностях
| Пункты Отправления | Пункты назначения | Запасы | ||||||||
| | | … | | |||||||
| | | | | | … | | | | ||
| | | | ||||||||
| | | | | | … | | | | ||
| | | | ||||||||
| … | … | … | … | … | … | |||||
| | | | | | … | | | | ||
| | | | ||||||||
| Потребности | | | … | | или | |||||
Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных
|
Требуется в области допустимых решений системы уравнений (3. ) и (3.) найти решение, минимизирующее линейную функцию (3. ).
Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен
На предприятии ОАО «Электросигнал» имеется 4 транзитных склада Аi, на которых хранятся сборочные узлы и 5 цехов Bj, занимающихся сборкой готовой продукции. Ниже, в таблице 3., приведены данные по количеству сборочных узлов на каждом складе, запросы цехов и стоимость перевозки одного агрегата из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок.
Таблица 3. – Исходные данные по количеству сборочных узлов и стоимость перевозки
| Склад | B1 (b1=40) | B2 (b2=50) | B3 (b3=15) | B4 (b4=75) | B5 (b5=40) |
| А1 (а1=50) | 1,0 | 2,0 | 3,0 | 2,5 | 3,5 |
| А2(а2=20) | 0,4 | 3,0 | 1,0 | 2,0 | 3,0 |
| А3(а3=75) | 0,7 | 1,0 | 1,0 | 0,8 | 1,5 |
| А4(а4=80) | 1,2 | 2,0 | 2,0 | 1,5 | 2,5 |
В данном случае Σai=225 >Σbj=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного цеха B6 с потребностью b5=225-220=5 и стоимостью перевозок сi6=0.Имеем таблицу 3. :
Таблица 3. -
| Цеха Склад | B1 (b1=40) | B2 (b2=50) | B3 (b3=15) | B4 (b4=75) | B5 (b5=40) | B6 (b6=5) |
| А1 (а1=50) | 1,0 | 2,0 | 3,0 | 2,5 | 3,5 | 0 |
| А2(а2=20) | 0,4 | 3,0 | 1,0 | 2,0 | 3,0 | 0 |
| А3(а3=75) | 0,7 | 1,0 | 1,0 | 0,8 | 1,5 | 0 |
| А4(а4=80) | 1,2 | 2,0 | 2,0 | 1,5 | 2,5 | 0 |
Математическая модель: обозначим xij – количество товара, перевозимого из Аi в Bj. Тогда
x21 x22 x23 x24 x25 x26
X = x31 x32 x33 x34 x35 x36 - матрица перевозок.
x41 x42 x43 x44 x45 x46
min(x11+2x12+3x13+2,5x14+3,5x15+0,4x21+3x22+x23+2x24+3x25+0,7x31+x32+x33+0,8x34+1,5x35++1,2x41+2x42+2x43+1,5x44+2,5x45) (3. )
x11+x12+x13+x14+x15+x16=50
x31+x32+x33+x34+x35+x36=75
x41+x42+x43+x44+x45+x46=80
|
x12+x22+x32+x42=50
x13+x23+x33+x43=15
x14+x24+x34+x44=75
x15+x25+x35+x45=40
x16+x26+x36+x46=5
xij≥0 (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3. )
Двойственная ЗЛП:
max(50u1+20u2+75u3+80u4+40v1+50v2+15v3+75v4+40v5+5v6) (3. )
|
|
| ||||||
u1+v2≤2
u1+v3≤3 (3. )
u1+v4≤2,5
u1+v5≤3,5
u1+v6≤0
ui,vj – произвольные (i=1,2,3,4 ; j=1,2,3,4,5,6 )
Будем искать первоначальный план по методу наименьшей стоимости:
1) x21=20 и 2-ую строку исключаем;
2) x31=20 и 1-ый столбец исключаем;
3) x34=55 и 3-ю строку исключаем;
4) x44=20 и 4-ый столбец исключаем;
5) x12=50 и 1-ю строку и 2-ой столбец исключаем и x32=0;
6) x43=150 и 3-ий столбец исключаем;
7) x45=40 и 5-ый столбец исключаем и x46=5.
Составим таблицу 3. . Здесь и далее в нижнем правом углу записываем значение перевозки.
Таблица 3. – Проведение итераций
| Склад | B1 (b1=40) | B2 (b2=50) | B3 (b3=15) | B4 (b4=75) | B5 (b5=40) | B6 (b6=5) | ||||||||
| А1 (а1=50) | 1,0 |
| 3,0 | 2,5 | 3,5 | 0 | ||||||||
| А2(а2=20) |
| 3,0 | 1,0 | 2,0 | 3,0 | 0 | ||||||||
| А3(а3=75) |
|
| 1,0 |
| 1,5 | 0 | ||||||||
| 1,2 | 2,0 | 2,0 |
|
| 0 |
