Оптимизация доставки грузов и плана выпуска промышленной продукции
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
Оглавление
1. Оптимизация доставки грузов
.1 Исходные данные
.2 Формирование схемы движения
.2.1 Составление начального плана перевозок
.2.2 Перераспределение ресурсов
.2.3 Перераспределение ресурсов
.2.4 Перераспределение ресурсов
.2.5 Перераспределение ресурсов
. Оптимизация плана выпуска промышленной продукции
.1 Исходные данные
.2 Постановка задачи
.3 Решение задачи симплекс методом
.3.1 Составление начального плана
.3.2 Решение задачи
. Выводы
.1 Транспортная задача
.2 План выпуска промышленной продукции
Список используемой литературы
1. Сущность оптимизации доставки грузов
Задача, решаемая в данной работе, относится к классу оптимизационных, функционал которой имеет экстремум. Поиск экстремума заключается в выборе оптимального варианта из множества вариантов прикрепления пунктов отправления и назначения грузов. Предполагается, что на всех направлениях осуществляются перевозки однородного груза.
Необходимо решить задачу связи пунктов отправления и назначения, обеспечив вывоз всех грузов из пункта отправления, ввоз во все пункты назначения требуемых объемов грузов и достижения минимального суммарного грузооборота.
1.1 Исходные данные
Таблица 1
Пункты отправленияОбъемы вывоза, тыс. тоннА1250А2450А3100
Таблица 2
Пункты назначенияОбъемы ввоза, тыс. тоннВ1150В280В3260В4120В5190
Таблица 3
Расстояния между пунктами, кмА1-В1270А1-В2190А1-В3290А1-В4190А1-В5180А2-В1175А2-В2350А2-В3200А2-В4185А2-В5200А3-В1230А3-В2310А3-В3295А3-В4200А3-В5325
1.2 Формирование схемы движения
Данная транспортная задача может быть решена методом потенциалов. Решается она на минимум грузооборота.
Целевая функция:
Где -расстояние между i-м пунктом отправления и j-м пунктом назначения(км);
-объем перевозок между i-м пунктом отправления
Ограничения:
=
Где -объем отправления из i-го пункта
-объем потребления в j-ом пунктеиндекс пункта отправления (i=1,…,m)индекс пункта назначения (j=1,…,n)число пунктов отправлениячисло пунктов назначения
1.2.1 Составление начального плана перевозок
Начальный (опорный) план перевозок будем искать методом северо-западного угла.
По этому методу заполнение клеток начинается с верхней левой клетки. Далее двигаемся вправо и вниз.
Первую клетку заполняем, исходя из следующего условия:
; ; и т.д.
Для любого опорного плана число свободных клеток равно (m-1)(n-1). Число базисных переменных (заполненных клеток) должно быть равно n+m-1, среди них могут оказаться нулевые значения.=5;m=3заполненных клеток 7, пустых клеток 8
Таблица4.
П. наз П. отпрВ1В2В3В4В5GiaiА1270 150190 80290 201901802500А2175350200 240185 120200 90450-90А3230310295200325 10010035Vj15080260120190bj270190290275290
F=L11x11+ L12x12+ L12x12+ L13x13+ L14x14+ L15x15+ L21x21+ L22x22+ L23x23+ L24x24+L25x25+ L31x31+ L32x32+ L33x33+ L34x34 + L35x35 =150*270+80*190 +20*290+ +0*190+0*180+0*175+0*350+240*200+120*185+90*200+0*230+0*310+0*295+0*200+100*325=182200
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
Значения потенциалов определяются из условия, что для базисных (заполненных) клеток сумма потенциалов равна расстоянию Lij, т.е.
+bij=Lij
при этом потенциал первого пункта отправления принимается равным 0 (а1=0)
а1=0=L11-a1=270-0=270=L12-a1=190-0=190=L13-a1=290-0=290=L23-b3=200-290= -90=L24-a2=185-(-90)=275=L25-a2=200-(-90)=290=L35-b5=325-290=35
б) проверяем условия оптимальности плана.
С целью проверки условий оптимальности плана для всех свободных клеток проверяется соотношение
aij+bijLij+b4=275>190!=85+b5=290>180!=110+b1=180>175!=5+b2=100200!=110
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
1.2.2 Перераспределение ресурсов
а) Строим в исходной матрице контур перераспределения ресурсов. Начало контура - клетка с максимальным нарушением условия оптимальности (клетка Х15). В новом плане эта клетка из незаполненной становится заполненной. Далее строим замкнутый многоугольник с вершинами в загруженных клетках, за исключением начала контура. Число вершин контура должно быть четным. Половина из них загружается и помечается знаком +, другая половина- разгружается и помечается знаком -.. в каждой строке и в каждом столбце имеется две вершины.
В контуре допускаются только вертикальные и горизонтальные линии.
В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных Хij ни одно из этих значений не должно превращаться в отрицательное число. Поэтому, с точки зрения переноса ресурсов по контуру анализируются только клетки, помеченные знаком -., из них выбирается клетка с минимальным объемом перевозок, и этот объем переносится по контуру.
Таблица5
П. наз П. отпрВ1В2В3В4В5GiaiА1270 150190 80290 20 -190180 +2500А2175350200 240 +185 120200 90 -450-90А3230310295200325 10010035Vj15080260120190bj270190290275290
Таблица6
П. наз П. отпрВ1В2В3В4В5GiaiА1270 150190 80290 190180 202500А2175350200 260185 120200 7045020А3230310295200325 100100145Vj15080260120190bj270190180165180
F=L11x11+ L12x12+ L12x12+ L13x13+ L14x14+ L15x15+ L21x21+ L22x22+ L23x23+ L24x24+L25x25+ L31x31+ L32x32+ L33x33+ L34x34 + L35x35 =150*270+80*190 +0*290+ +0*190+20*180+0*175+0*350+260*200+120*185+70*200+0*230+0*310+0*295+0*200+100*325=180000
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
aij+bij=Lij
а1=0=L11-a1=270-0=270=L12-a1=190-0=190=L15-a1=180-0=180=L25-b5=200-180= 20=L23-a2=200-20=180
b4=L24-a2=185-20=165=L35-b5=325-180=145
б) проверяем условия оптимальности плана.
aij+bijLij+b3=180200!=110
Ус?/p>