Содержание
1. Постановка задачи
· Формирование схемы движения. Транспортная задача
· Оптимизация плана выпуска промышленной продукции. Симплекс-метод
2. Транспортная задача
3. Симплекс-метод
1. Постановка задачи
Формирование схемы движения (Транспортная задача)
Задача, решаемая в курсовой работе, относиться к классу оптимизационных, функционал которой имеет экстремум. Поиск экстремума заключается в выборе оптимального варианта из множества вариантов прикрепления пунктов отправления и назначения грузов. Предполагается, что на всех направлениях осуществляются перевозки однородного груза и в этой части проблема сводиться к решению однопродуктовой транспортной задачи.
Необходимо решить задачу связи пунктов отправления и назначения, обеспечив вывоз всех грузов из пункта отправления, ввоз во все пункты назначения требуемых объемов грузов и достижения минимального суммарного грузооборота.
Оптимизация плана выпуска промышленной продукции
В этом разделе разрабатывается оптимальный план выпуска промышленной продукции. Задача формируется следующим образом: для выпуска четырех видов продукции требуются затраты сырья, рабочего времени и оборудования. Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный план выпуска продукции.
Необходимо определить искомые переменные, расписать математическую постановку задачи и решить ее симплекс-методом.
В заключительном разделе курсовой работы необходимо расшифровать полученные результаты, обосновать оптимальность и допустимость полученного решения и сделать выводы.
Задание №22
Транспортная задача.
Исходные данные:
Пункты отправления Объем ввоза, тыс. тонн А 50 Г 100 Е 350 Пункты назначения Объем ввоза, тыс. тонн К 70 Л 130 М 50 Н 150 П 100
Расстояния между пунктами, км:
А-К 350 Г-К 220 Е-К 200 А-Л 400 Г-Л 290 Е-Л 240 А-М 340 Г-М 160 Е-М 235 А-Н 230 Г-Н 260 Е-Н 150 А-П 180 Г-П 255 Е-П 225
Используя метод северо-западного угла, составляем первоначальный план перевозок и проверяем на оптимальность:
Bj
К=70
Л=130
М=50
Н=150
П=100
Ui
Ai
А=50
50
350
-
400
-
340
-
230
-
180
405
Г=100
20
220
80
290
-
160
-
260
-
255
275
Е=350
-
200
50
240
50
235
150
150
100
225
225
Vj
-55
15
10
-75
0
Определяются потенциальные оценки свободных клеток:
12= 20 23= 125 13= 75 24= -60 14= 100 25= 55 15= 225 31= -30
План перевозок не оптимален, поскольку имеются положительные потенциальные оценки, а значение целевой функции:
Z=50*350+20*220+80*290+50*240+50*235+150*150+100*225=113850
Может быть улучшено.
Выбираем цикл с включением в качестве вершины клетки с потенциальной оценкой +125, что позволяет перераспределить перевозки:
80
80
-
30
80
50
130 50 130 50
50
100
50
100
100
-
и получить новый план перевозок в виде очередной таблице:
Bj
К=70
Л=130
М=50
Н=150
П=100
Ui
Ai
А=50
50
350
-
400
-
340
-
230
-
180
405
Г=100
20
220
30
290
50
160
-
260
-
255
275
Е=350
-
200
100
240
-
235
150
150
100
225
225
Vj
-55
15
-115
-75
0
Полученный план так же не оптимален, так как среди потенциальных оценок свободных клеток есть положительные:
12= 20 24= -60 13= -50 25= 55 14= 100 31= -30 15= 225 33= -125
При этом значение целевой функции:
Z=50*350+20*220+30*290+100*240+50*160+150*150+100*225=107600
Улучшилось.
Снова выбираем цикл с включением в качестве вершины клетки с потенциальной оценкой +20, что позволяет перераспределить перевозки:
50
50
-
20
50
30
70 30 70 30
20
50
30
50
50
-
и получить новый план перевозок в виде очередной таблице:
Bj
К=70
Л=130
М=50
Н=150
П=100
Ui
Ai
А=50
20
350
30
400
-
340
-
230
-
180
385
Г=100
50
220
-
290
50
160
-
260
-
255
255
Е=350
-
200
100
240
-
235
150
150
100
225
225
Vj
-35
15
-95
-75
0
Полученный план так же не оптимален, так как среди потенциальных оценок свободных клеток есть положительные:
13= -50 24= -60 14= 80 25= 55 15= 205 31= -30 22= -20 33= -125
При этом значение целевой функции:
Z=20*350+50*220+30*400+100*240+50*160+150*150+100*225=107000
Улучшилось.
Снова выбираем цикл с включением в качестве вершины клетки с потенциальной оценкой +80, что позволяет перераспределить перевозки:
30
30
-
-
30
30
130 150 130 150
100
250
150
130
250
120
и получить новый план перевозок в виде очередной таблице:
Bj
К=70
Л=130
М=50
Н=150
П=100
Ui
Ai
А=50
20
350
-
400
-
340
30
230
-
180
305
Г=100
50
220
-
290
50
160
-
260
-
255
175
Е=350
-
200
130
240
-
235
120
150
100
225
225
Vj
45
15
-15
-75
0
Полученный план так же не оптимален, так как среди потенциальных оценок свободных клеток есть положительные:
12= -80 24= -160 13= -50 25= -80 15= 125 31= 70 22= -100 33= -25
При этом значение целевой функции:
Z=20*350+50*220+130*240+50*160+30*230+120*150+100*225=104600
Улучшилось.
Снова выбираем цикл с включением в качестве вершины клетки с потенциальной оценкой +125, что позволяет перераспределить перевозки:
30
30
-
-
30
30
150 100 150 100
120
220
100
150
220
70
и получить новый план перевозок в виде очередной таблице:
Bj
К=70
Л=130
М=50
Н=150
П=100
Ui
Ai
А=50
20
350
-
400
-
340
-
230
30
180
180
Г=100
50
220
-
290
50
160
-
260
-
255
50
Е=350
-
200
130
240
-
235
150
150
70
225
225
Vj
170
15
110
-75
0
Полученный план так же не оптимален, так как среди потенциальных оценок свободных клеток есть положительные:
12= -205 24= -285 13= -50 25= -205 14= -125 31= 195 22= -225 33= 100
При этом значение целевой функции:
Z=20*350+50*220+130*240+50*160+150*150+30*180+70*225=100850
Улучшилось.
Снова выбираем цикл с включением в качестве вершины клетки с потенциальной оценкой +195, что позволяет перераспределить перевозки:
20
50
30
-
50
50
20 100 20 100
-
70
70
20
70
50
и получить новый план перевозок в виде очередной таблице:
Bj
К=70
Л=130
М=50
Н=150
П=100
Ui
Ai
А=50
-
350
-
400
-
340
-
230
50
180
180
Г=100
50
220
-
290
50
160
-
260
-
255
245
Е=350
20
200
130
240
-
235
150
150
50
225
225
Vj
-25
15
-85
-75
0
11= -195 22= -30 12= -205 24= -90 13= -245 25= -10 14= -125 33= -95
Z=50*220+20*200+130*240+50*160+150*150+50*180+50*225=96950
Таким образом, получен оптимальный план перевозок.
Симплекс-метод
Исходные данные:
Тип ресурса
Нормы затрат ресурсов на единицу продукции
Запасы ресурсов
1
2
3
4
Сырье 6 4 3 5 70 Рабочее время 23 15 19 31 450 Оборудование 11 15 8 17 140 Прибыль на единицу продукции 31 26 9 17
На основе исходных данных составляется математическая модель задачи:
Для решения задачи симплекс-методом необходимы очевидные промежуточные преобразования:
Если выбрать в качестве базисных переменных введенные дополнительные переменные , , то последняя модель переписывается в виде:
В итоге формируется симплекс-таблица следующего вида:
П
БП
1
6 4 3 5 70
23 15 19 31 450
11 15 8 17 140
-31 -26 -9 -17 0
Решение не оптимально. ............
