Оптимизация доставки грузов и плана выпуска промышленной продукции
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
»овие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
1.2.3 Перераспределение ресурсов
Клетка с максимальным нарушением условия оптимальности- Х31
Таблица 7
П. наз П. отпрВ1В2В3В4В5GiaiА1270 150 -190 80290 190180 20 +2500А2175350200 260185 120200 7045020А3230 +310295200325 100 -100145Vj15080260120190bj270190180165180
Таблица8
П. наз П. отпрВ1В2В3В4В5GiaiА1270 50190 80290 190180 1202500А2175350200 260185 120200 7045020А3230 100310295200325100-40Vj15080260120190bj270190180165180
F=L11x11+ L12x12+ L12x12+ L13x13+ L14x14+ L15x15+ L21x21+ L22x22+ L23x23+ L24x24+L25x25+ L31x31+ L32x32+ L33x33+ L34x34 + L35x35 =50*270+80*190 +0*290+ +0*190+120*180+0*175+0*350+260*200+120*185+70*200+100*230+0*310+0*295+0*200+0*325=161500
а) Определяем потенциалы пунктов отправления 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=L24-a2=185-20=165
b3=L23-a2=200-20=180=L31-b1=230-270=230-270=-40
б) проверяем условия оптимальности плана.
aij+bijLij+b3=180175!=115+b2=210<350+b2=150<310+b3=140<2953+b4=125<200
a3+b5=140<325
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
1.2.4 Перераспределение ресурсов
Клетка с максимальным нарушением условия оптимальности- Х21
Таблица9
П. наз П. отпрВ1В2В3В4В5GiaiА1270 50 -190 80 290190180 120 +2500А2175 +350200 260185 120200 70 -45020А3230 100310295200325100-40Vj15080260120190bj270190180165180
Таблица10
П. наз П. отпрВ1В2В3В4В5GiaiА1270190 80290190180 1702500А2175 50350200 260185 120200 2045020А3230 100310295200325 10075Vj15080260120190bj155190180165180
F=L11x11+ L12x12+ L12x12+ L13x13+ L14x14+ L15x15+ L21x21+ L22x22+ L23x23+ L24x24+L25x25+ L31x31+ L32x32+ L33x33+ L34x34 + L35x35 =0*270+80*190 +0*290+ +0*190+170*180+50*175+0*350+260*200+120*185+20*200+1000*230+0*310+0*295+0*200+0*325=155750
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
aij+bij=Lij
а1=0=L12-a1=190-0=190=L15-a1=180-0=180=L25-b5=200-180=20=L21-a2=175-20= 155=L23-a2=200-20=180
b4=L24-a2=185-20=165=L31-b1=230-155=75
б) проверяем условия оптимальности плана.
aij+bijLij+b1=155<270+b3=180<290+b4=165<190+b2=210<350+b2=265<310+b3=255<295
a3+b4=240>200! =40+b5=255<325
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
1.2.5 Перераспределение ресурсов
Клетка с максимальным нарушением условия оптимальности- Х34
Таблица11
П. наз П. отпрВ1В2В3В4В5GiaiА1270190 80290190180 1702500А2175 50 +350200 260185 - 120200 2045020А3230 100 -310295200 +32510075Vj15080260120190bj155190180165180
Таблица12
П. наз П. отпрВ1В2В3В4В5GiaiА1270190 80290190180 1702500А2175 150350200 260185 20200 2045020А3230310295200 10032510075Vj15080260120190bj155190180165180
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
aij+bij=Lij
а1=0=L12-a1=190-0=190=L15-a1=180-0=180=L25-b5=200-180=20=L21-a2=175-20= 155=L23-a2=200-20=180
b4=L24-a2=185-20=165=L34-b4=200-165=35
б) проверяем условия оптимальности плана.
aij+bijLij+b1=155<270+b3=180<290+b4=165<190+b2=210<350+b1=190<230+b2=255<310
a3+b3=215<295+b5=215<325
Условия оптимальности выполнены, т.е. данный план обеспечивает минимальный суммарный грузооборот.
Проверяем ограничения:
а) N=n+m-1=5+3-1=7
б) x11+x12+x13+x14+x15=0+80+0+0+170=250+x22+x23+x24+x25=150+0+260+20+20=450+x32+x33+x34+x35=0+0+0+100+0=100+x21+x31=0+150+0=150+x22+x32=80+0+0=80+x23+x33=0+260+0=260+x24+x34=0+20+100=120+x25+x35=170+20+0=190
в) Xij0
F=L11x11+ L12x12+ L12x12+ L13x13+ L14x14+ L15x15+ L21x21+ L22x22+ L23x23+ L24x24+L25x25+ L31x31+ L32x32+ L33x33+ L34x34 + L35x35 =0*270+80*190 +0*290+ +0*190+170*180+150*175+0*350+260*200+20*185+20*200+0*230+0*310+0*295+100*200+0*325=151750
2. Оптимизация плана выпуска промышленной продукции
Задача: для выпуска четырех видов продукции требуются запасы сырья, рабочего времени и оборудования. Необходимо сформулировать экономико-математическую модель задачи на максимум прибыли, найти оптимальный план выпуска продукции.
2.1 Исходные данные
груз экономический математический прибыль
Таблица13
Тип ресурсаНормы затрат ресурсов на единицу продукцииЗапасы ресурсов1234Сырье10948120Рабочее время44283660800Оборудование20281632400Прибыль на единицу продукции60504032
2.2 Постановка задачи
Искомая переменная:
Х-количество выпускаемой продукции
Целевая функция:
=60X1+50X2+40X3+32X4>max
Ограничения:
;X2;X3;X4?0
X1+9X2+4X3+8X4?120
X1+28X2+36X3+60X4?800
X1+28X2+16X3+32X4?400
2.3 Решение задачи симплекс методом
.3.1 Составление начального плана
Так как в ограничениях нашей задачи левая часть меньше или равна правой, то неравенства мы преобразуем в равенства (кроме первого) путем добавления свободных переменных, коэффициент которых равен 1.
X1+9X2+4X3+8X4+Х5?120; Х5-неиспользованное сырье
X1+28X2+36X3+60X4+Х6?800; Х6-неиспользованное время
X1+28X2+16X3+32X4+Х7?400; Х7-неиспользуемое оборудование.
С экономической точки зрения свободные переменные представляют собой неиспользованные ресурсы, поэтому их цена в целевой функции равна 0.
Коэффициенты при свободных переменных образуют единичную матрицу, определитель которой равен 1. Векторы, составленные из коэффициентов при свободных переменных образуют базис
Таблица14
Cj60504032000CiБазисP0X1X2X3X4X5X6X70X5120109481000X6800442836600100X740020281632001Zj0000000Zj-Cj-60-50-40-32000=0*120+0*800+0*400=0
Cj-признак оптимальности в симплекс таблице. Если задача решается на максимум, то план явуляется оптимальным, если Zj-Cj ?0
2.3.2 Решение задачи
1) План 1
а) Определяем вектор (столбец), который вводится в базис. Это вектор с максимальным нарушением оптимальности (по модулю). Индекс ключевого столбца-k
60;50;40;32;0;0;0=60ключевой столбец-Х1
б) Определяем вектор (строку), который выводится из базиса. Это строка, в которой имеет место соотношение:
?=min, Xik >0
вектор решениячисло, стоящее на пересечении i-ой строки и ключевого столбца
Инднекс ключевой стоки-r. Элемент таблицы, находящийся на пересечении ключевого столбца и ключевой строки, называется генеральным, и обозначается Xrk
?=min=min=12кл?/p>