Реферат: Улучшение системы выпуска товаров
Содержание
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
8050
130 50 130 5050
10050
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
5030
70 30 70 3020
5030
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-
-
3030
130 150 130 150100
250150
130
250120
и получить новый планперевозок в виде очередной таблице:
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-
-
3030
150 100 150 100120
220100
150
22070
и получить новый планперевозок в виде очередной таблице:
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
5030
-
5050
20 100 20 100-
7070
20
7050
и получить новый планперевозок в виде очередной таблице:
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,72Z=
-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,52Z=
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,52Z=
3,89 0,69 8,23 14,28 369,78Согласно полученнымданным оптимальным является распределение заказа между 10,65 станками первоготипа и 182,17 станками шестого типа. При минимальных издержках в 369,78 ден.единиц.