Экономико-математическое моделирование : Улучшение системы выпуска товаров
Улучшение системы выпуска товаров
12 Содержание 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 | | |
Решение не оптимально. В строке 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 | 0 | | | | | | | | | | | |
При выборе разрешающими столбца и строки Х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 ден. единиц.
|