Автор работы: Пользователь скрыл имя, 27 Января 2014 в 16:15, курсовая работа
Цели курсовой работы:
- показать, как разрабатываются математические модели двухэтапных транспортных задач линейного программирования;
- решить сформулированные математические задачи на ЭВМ с использованием пакетов прикладных программ линейного программирования.
Определить объемы производства каждого поставщика, какие склады и с какой пропускной способностью требуется построить, направление и объемы поставки товаров на склады, а со складов к потребителям, которые удовлетворяли бы всем имеющимся условиям и обеспечивали минимальные суммарные затраты на поставку при условии, что все потребности будут удовлетворены.
1. Решить двухэтапную транспортную задачу
2. Решить эту же задачу путем раздельного прикрепления поставщиков к складам и складов к потребителям
Из А3 в Д4 перевозки не осуществляются и из Д4 в В2 перевозки так же запрещены,
Из Д6 в В5 можно перевезти не более 50 единиц груза.
Оценить и проанализировать раздельное влияние этих ограничений и общее их влияние на затраты.
5. Решить задачи п.1, п.2 и п. 4 (4 задачи) с использованием ЭВМ.
2.1. Решим двухэтапную транспортную задачу.
Обозначим через Xik – количество продукции, поставляемое от i-го пункта производства на к-й промежуточный пункт (i=1, 2, 3, 4, 5; k= 1, 2, 3, 4, 5, 6), а через Xkj - количество продукции, поставляемое с к-го промежуточного пункта j-му потребителю (k= 1, 2, 3, 4, 5, 6; j=1, 2, 3,4, 5, 6). Тогда целевая функция, характеризующая суммарные транспортные расходы, запишется в виде:
Ограничения запишутся в виде:
Условия положительности переменных:
Xik³0 (i=1, 2, 3, 4, 5; k= 1, 2, 3, 4, 5, 6); Xkj³0 (k= 1, 2, 3, 4, 5, 6; j=1, 2, 3,4, 5, 6).
Так как 800, то можно решать двухэтапную транспортную задачу. Определяем число заполненных клеток первоначального опорного плана: 11 + 12 – 1 = 22.
Составляем начальный опорный план методом минимального элемента. Вначале заполняем первый или четвертый квадрант, затем третий, а затем оставшийся (первый или четвертый). В таблице 2.1 получен первоначальный опорный план. Проверим полученный план на оптимальность, для этого находим потенциалы Ui и Vj.
После того как мы определили потенциалы Ui и Vj, находим оценки свободных клеток:
S83 = 0 – (1+0) = -1; S8 10 = 1 – (1+2) = -2; и так далее.
Полученный опорный план не оптимален, так как имеются отрицательные оценки, наибольшая по модулю из них S8 10. Строим для заданной клетки замкнутый контур и улучшаем, полученный опорный план.
В результате получаем таблицу 2.2.
После того как мы определили потенциалы Ui и Vj, находим оценки свободных клеток:
S83 = 0 – (1+0) = -1; S8 12 = 4 – (4+1) = -1; и так далее.
Полученный опорный план не оптимален, так как имеются отрицательные оценки, наибольшая по модулю из них S83 и S8 12. Строим для клетки S8 12 замкнутый контур и улучшаем, полученный опорный план.
В результате получаем таблицу 2.3.
Поскольку в таблице 2.3 нет свободных клеток с отрицательными оценками, то мы получили оптимальный план. В таблице 2.3 имеются нулевые оценки свободных клеток, следовательно, полученный нами оптимальный план не является единственным. Данному плану отвечают минимальные затраты, величина которых составляет:
f= (50∙3 + 70∙1 + 80∙1 + 140∙2 + 160∙1 + 30∙1+ 20∙3 + 200∙2 + 50∙1) + (100∙2 + 30∙1 + 70∙1 + 160∙2 + 80∙1+ 10∙2 + 120∙1 + 30∙2 + 100∙1 + 100∙3) = 1280 + 1300 = 2580 ден. ед.
2.2. Решим задачу путем раздельного прикрепления поставщиков к складам и складов к потребителям.
Запишем начальные условия первого этапа задачи в форме табл. 2.3.
Таблица.2.4
Мощности поставщиков Аi |
Промежуточные пункты и их спрос Dk | |||||
|
D1 (100) |
D2 (30) |
D3 (70) |
D4 (240) |
D5 (160) |
D6 (200) | |
А1 (120) |
3 X11 |
5 X12 |
1 X13 |
4 X14 |
2 X15 |
3 X16 |
|
А2 (80) |
5 X21 |
6 X22 |
4 X23 |
1 X24 |
8 X25 |
3 X26 |
|
А3 (300) |
3 X31 |
1 X32 |
5 X33 |
2 X34 |
1 X35 |
3 X36 |
|
А4 (250) |
6 X41 |
1 X42 |
4 X43 |
3 X44 |
5 X45 |
2 X46 |
|
А5 (50) |
1 X51 |
3 X52 |
5 X53 |
2 X54 |
8 X55 |
4 X56 |
Составим математическую модель задачи.
Обозначим через Хik (i = 1,5; k = 1,6) объем продукции, который планируется перевезти от поставщика Аi, в промежуточный пункт Dk, а через f1 - общие затраты на первом этапе транспортировки.
Целевая функция задачи запишется в виде:
f1=3• X11 + 5 • X12 +...+ 4•X56 (min) (2.2.1)
Сравнивая суммарную мощность поставщиков 120 + 80 + 300 + 250 + 50 = 800 со спросом на промежуточных пунктах 100 + 30 + 70 + 240 + 160 + 200 = 800, видим, что эти суммы совпадают. Следовательно, данная транспортная задача обладает закрытой моделью.
Переходя к ограничениям на переменные Хik, следует учесть, что спрос на промежуточных пунктах Dk, не может превышать мощности поставщиков, т.е.
X11 + X12 + X13 + X14 + X15 + X16 =120
X21 + X22 + X23 + X24 + X25 + X26 = 80 (2.2.2)
X31 + X32+ X33 + X34+ X35 + X36 = 300
X41 + X42+ X43 + X44+ X45 + X46 = 250
X51 + X52+ X53 + X54+ X55 + X56 = 50
Условия удовлетворения спроса на промежуточных пунктах Dk:
X11 + X21 + X31+ X41+ X51 = 100
X12 + X22 + X32 + X42+ X52 = 30
X13 + X23+ X33+ X43+ X53 =70
X14 + X24+ X34+ X44 +
X54 = 240
X15 + X25+ X35+ X45 + X55 = 160
X16 + X26+ X36+ X46 + X56 = 200
Условия неотрицательности переменных:
Хij ≥0 (i=1,5; k=1,6)
Соотношения (2.2.1) - (2.2.4) образуют экономико-математическую модель рассматриваемой задачи. Таким образом, математическая модель задачи: целевая функция (2.2.1), описывающая суммарные затраты на первом этапе транспортировки, минимизируется при ограничениях (2.2.2) - (2.2.4).
Решим полученную задачу методом потенциалов.
Таблица 2.5
D1 (100) |
D2 (30) |
D3 (70) |
D4 (240) |
D5 (160) |
D6 (200) |
Ui | |
|
А1 (120) |
3 50 |
5 |
1 70 |
4 |
2 0 |
3 |
0 |
А2 (80) |
5 |
6 |
4 |
1 80 |
8 |
3 |
-2 |
А3 (300) |
3 |
1 |
5 |
2 140 |
1 160 |
3 |
-1 |
А4 (250) |
6 |
1 30 |
4 |
3 20 |
5 |
2 200 |
0 |
А5 (50) |
1 50 |
3 |
5 |
2 |
8 |
4 |
-2 |
Vj |
3 |
1 |
1 |
3 |
2 |
2 |
Приступая к составлению исходного опорного плана, устанавливаем, что в нашем случае любой опорный план должен «загружать» m+n-1= 5+6-1=10 клеток.
Построим исходный опорный план методом минимального элемента.
Для исследования плана
на оптимальность необходимо найти
оценки свободных клеток. Для этого надо знать потенциалы
Ui и Vj, которые определяются
в результате решения системы уравнений
U1 + V1 = 3
U1 + V3 = 1
U1 + V5 = 2
U2 + V4 =1
U3 + V4 =2
U3 + V5 = 1
U4 + V2 = 1
U4 + V4 = 3
U4 + V6 = 2
U5 + V1 = 1
составленных по заполненным клеткам. Это неопределенная система, т.к. неизвестных на одно больше числа уравнений. Придадим одному из неизвестных определенное числовое значение, например, U4 = 0. Тогда остальные неизвестные находятся из системы.
Получаем
U1 = 0, U2 = -2, U3 = -1, U4 = 0, U5 = -2, V1 = 3, V2 = 1, V3 = 1, V4 = 3, V5 = 2, V6 = 2.
Теперь можно найти оценки свободных клеток: Δ12 = C12 - (U1 + V2) = 5-(1 + 0)= 4, Δ14= 1, Δ16 = 1, Δ21 = 4, Δ22 = 7, Δ23 = 5, Δ25 = 8, Δ26= 3, Δ31= 1, Δ32= 1, Δ33 = 5, Δ36= 2 и т. Д.
Поскольку в табл. 2.5 свободных клеток с отрицательными оценками нет, то опорный план является оптимальным. Итак, получен оптимальный план:
50 |
0 |
70 |
0 |
0 |
0 | |
0 |
0 |
0 |
80 |
0 |
0 | |
X*= |
0 |
0 |
0 |
140 |
160 |
0 |
0 |
30 |
0 |
20 |
0 |
200 | |
50 |
0 |
0 |
0 |
0 |
0 |
Этому плану соответствуют минимальные суммарные затраты в 1280 ден. ед.
(f1= 50∙3 + 70∙1 + 80∙1 + 140∙2 + 160∙1 + 30∙1+ 20∙3 + 200∙2 + 50∙1 = 1280)
Запишем начальные условия второго этапа задачи в форме таблицы 2.6.
Таблица 2.6
Возможности промежуточных пунктов Dk |
Пункты потребления и их спрос Вj | |||||
|
В1 (40) |
В2 (160) |
В3 (120) |
В4 (150) |
В5 (130) |
В6 (200) | |
D1 (100) |
9 X11 |
3 X12 |
4 X13 |
1 X14 |
5 X15 |
2 X16 |
|
D2 (30) |
1 X21 |
6 X22 |
2 X23 |
5 X24 |
3 X25 |
8 X26 |
|
D3 (70) |
3 X31 |
5 X32 |
2 X33 |
1 X34 |
3 X35 |
4 X36 |
|
D4 (240) |
7 X41 |
2 X42 |
5 X43 |
1 X44 |
4 X45 |
6 X46 |
|
D5 (160) |
2 X51 |
3 X52 |
1 X53 |
4 X54 |
2 X55 |
8 X56 |
|
D6 (200) |
5 X61 |
3 X62 |
2 X63 |
4 X64 |
1 X65 |
3 X66 |
Обозначим через Хkj (k = 1,6; j = 1,6) объем продукции, который планируется перевезти из промежуточного пункта Dk к потребителю bj, а через f2 - общие затраты на втором этапе транспортировки.