Содержание
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
Определяютсяпотенциальные оценки свободных клеток: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
Полученный план так же неоптимален, так как среди потенциальных оценок свободных клеток естьположительные: 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
Полученный план так же неоптимален, так как среди потенциальных оценок свободных клеток естьположительные: 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
Полученный план так же неоптимален, так как среди потенциальных оценок свободных клеток естьположительные: 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
Полученный план так же неоптимален, так как среди потенциальных оценок свободных клеток естьположительные:
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
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
Решение не оптимально. Встроке Z присутствуют отрицательныекоэффициенты. Выбираем разрешающий столбец с максимальным отрицательнымзначением />. Для выбора разрешающестроки свободные коэффициенты (70, 450, 140) делят на элементы разрешающегостолбца. По минимальному положительному отношению выбирается разрешающая строка/>. Пересечение разрешающегостолбца и строка дает разрешающий инструмент (=6)
БП/П
(-Х1)
(-Х2)
(-Х3)
(-Х4)
1
Х5= 6 4 3 5 70 11,6
Х6= 23 15 19 31 450 19,56
Х7= 11 15 8 17 140 12,72
Z= -31 -26 -9 -17
При выборе разрешающимистолбца /> и строки Х5 получаем новуюсимплекс-таблицу:
БП/П
(-Х5)
(-Х2)
(-Х3)
(-Х4)
1
Х1= 0,16 0,66 0,5 0,83 11,66 17,66
Х6= -3,83 -0,33 7,5 11,83 181,66 -550,48
Х7= -1,83 7,66 2,5 7,83 11,66 1,52
Z= 5,16 -5,33 6,5 8,83 361,66
БП/П
(-Х5)
(-Х7)
(-Х3)
(-Х4)
1
Х1= 0,32 -0,08 0,28 0,152 10,65
Х6= -3,91 0,04 7,6 12,17 182,17
Х2= -0,23 0,13 0,32 1,02 1,52
Z= 3,89 0,69 8,23 14,28 369,78
Согласно полученнымданным оптимальным является распределение заказа между 10,65 станками первоготипа и 182,17 станками шестого типа. При минимальных издержках в 369,78 ден.единиц.