Оптимизация доставки грузов и плана выпуска промышленной продукции

Задача, решаемая в данной работе, относится к классу оптимизационных, функционал которой имеет экстремум. Поиск экстремума заключается в выборе оптимального варианта из множества вариантов прикрепления пунктов отправления и назначения грузов. Предполагается, что на всех направлениях осуществляются перевозки однородного груза.

Необходимо решить задачу связи пунктов отправления и назначения, обеспечив вывоз всех грузов из пункта отправления, ввоз во все пункты назначения требуемых объемов грузов и достижения минимального суммарного грузооборота.

1.1 Исходные данные

Начальный (опорный) план перевозок будем искать методом северо-западного угла.

По этому методу заполнение клеток начинается с верхней левой клетки. Далее двигаемся вправо и вниз.

Первую клетку заполняем, исходя из следующего условия:

; ; и т.д.

Для любого опорного плана число свободных клеток равно (m-1)(n-1). Число базисных переменных (заполненных клеток) должно быть равно n+m-1, среди них могут оказаться нулевые значения.

n=5;m=3заполненных клеток 7, пустых клеток 8

Таблица4.

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, т.е.

aij+bij=Lij

при этом потенциал первого пункта отправления принимается равным 0 (а1=0)

а1=0

b1=L11-a1=270-0=270

b2=L12-a1=190-0=190

b3=L13-a1=290-0=290

a2=L23-b3=200-290= -90

b4=L24-a2=185-(-90)=275

b5=L25-a2=200-(-90)=290

a3=L35-b5=325-290=35

б) проверяем условия оптимальности плана.

С целью проверки условий оптимальности плана для всех свободных клеток проверяется соотношение

aij+bijLij

a1+b4=275>190!=85

a1+b5=290>180!=110

a2+b1=180>175!=5

a2+b2=100<350

a3+b1=305>230!=75

a3+b2=225<310

a3+b3=325>295!=30

a3+b4=310>200!=110

Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.

1.2.2 Перераспределение ресурсов

а) Строим в исходной матрице контур перераспределения ресурсов. Начало контура - клетка с максимальным нарушением условия оптимальности (клетка Х15). В новом плане эта клетка из незаполненной становится заполненной. Далее строим замкнутый многоугольник с вершинами в загруженных клетках, за исключением начала контура. Число вершин контура должно быть четным. Половина из них загружается и помечается знаком «+», другая половина- разгружается и помечается знаком « -.». в каждой строке и в каждом столбце имеется две вершины.

В контуре допускаются только вертикальные и горизонтальные линии.

В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных Хij ни одно из этих значений не должно превращаться в отрицательное число. Поэтому, с точки зрения переноса ресурсов по контуру анализируются только клетки, помеченные знаком « -.», из них выбирается клетка с минимальным объемом перевозок, и этот объем переносится по контуру.

Таблица5

Таблица6

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

b1=L11-a1=270-0=270

b2=L12-a1=190-0=190

b5=L15-a1=180-0=180

a2=L25-b5=200-180= 20

b3=L23-a2=200-20=180

b4=L24-a2=185-20=165

a3=L35-b5=325-180=145

б) проверяем условия оптимальности плана.

aij+bijLij

a1+b3=180<190

a1+b4=165<190

a2+b1=290>175!=115

a2+b2=210<350

a3+b1=415>230!=185

a3+b2=335>310!=25

a3+b3=325>295!=30

a3+b4=310>200!=110

Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.

1.2.3 Перераспределение ресурсов

Клетка с максимальным нарушением условия оптимальности- Х31

Таблица 7

Таблица8

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

b1=L11-a1=270-0=270

b2=L12-a1=190-0=190

b5=L15-a1=180-0=180

a2=L25-b5=200-180= 20

b4=L24-a2=185-20=165

b3=L23-a2=200-20=180

a3=L31-b1=230-270=230-270=-40

б) проверяем условия оптимальности плана.

aij+bijLij

a1+b3=180<290

a1+b4=165<180

a2+b1=290>175!=115

a2+b2=210<350

a3+b2=150<310

a3+b3=140<295

a3+b4=125<200

a3+b5=140<325

Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.

1.2.4 Перераспределение ресурсов

Клетка с максимальным нарушением условия оптимальности- Х21

Таблица9

Таблица10

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

b2=L12-a1=190-0=190

b5=L15-a1=180-0=180

a2=L25-b5=200-180=20

b1=L21-a2=175-20= 155

b3=L23-a2=200-20=180

b4=L24-a2=185-20=165

a3=L31-b1=230-155=75

б) проверяем условия оптимальности плана.

aij+bijLij

a1+b1=155<270

a1+b3=180<290

a1+b4=165<190

a2+b2=210<350

a3+b2=265<310

a3+b3=255<295

a3+b4=240>200! =40

a3+b5=255<325

Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.

1.2.5 Перераспределение ресурсов

Клетка с максимальным нарушением условия оптимальности- Х34

Таблица11

Таблица12

а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj

aij+bij=Lij

а1=0

b2=L12-a1=190-0=190

b5=L15-a1=180-0=180

a2=L25-b5=200-180=20

b1=L21-a2=175-20= 155

b3=L23-a2=200-20=180

b4=L24-a2=185-20=165

a3=L34-b4=200-165=35

б) проверяем условия оптимальности плана.

aij+bijLij

a1+b1=155<270

a1+b3=180<290

a1+b4=165<190

a2+b2=210<350

a3+b1=190<230

a3+b2=255<310

a3+b3=215<295

a3+b5=215<325

Условия оптимальности выполнены, т.е. данный план обеспечивает минимальный суммарный грузооборот.

Проверяем ограничения:

а) N=n+m-1=5+3-1=7

б) x11+x12+x13+x14+x15=0+80+0+0+170=250

x21+x22+x23+x24+x25=150+0+260+20+20=450

x31+x32+x33+x34+x35=0+0+0+100+0=100

x11+x21+x31=0+150+0=150

x12+x22+x32=80+0+0=80

x13+x23+x33=0+260+0=260

x14+x24+x34=0+20+100=120

x15+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

2.2 Постановка задачи

2.3.1 Составление начального плана

Так как в ограничениях нашей задачи левая часть меньше или равна правой, то неравенства мы преобразуем в равенства (кроме первого) путем добавления свободных переменных, коэффициент которых равен 1.

10X1+9X2+4X3+8X4+Х5?120; Х5--неиспользованное сырье

44X1+28X2+36X3+60X4+Х6?800; Х6--неиспользованное время

20X1+28X2+16X3+32X4+Х7?400; Х7--неиспользуемое оборудование.

С экономической точки зрения свободные переменные представляют собой неиспользованные ресурсы, поэтому их цена в целевой функции равна 0.

Коэффициенты при свободных переменных образуют единичную матрицу, определитель которой равен 1. Векторы, составленные из коэффициентов при свободных переменных образуют базис

Таблица14

Z=0*120+0*800+0*400=0

Zj-Cj--признак оптимальности в симплекс таблице. Если задача решается на максимум, то план явуляется оптимальным, если Zj-Cj ?0

2.3.2 Решение задачи

1) План 1

а) Определяем вектор (столбец), который вводится в базис. Это вектор с максимальным нарушением оптимальности (по модулю). Индекс ключевого столбца-k

max60;50;40;32;0;0;0=60ключевой столбец--Х1

б) Определяем вектор (строку), который выводится из базиса. Это строка, в которой имеет место соотношение:

И=min, Xik >0

Xi--вектор решения

Xik--число, стоящее на пересечении i-ой строки и ключевого столбца

Инднекс ключевой стоки-r. Элемент таблицы, находящийся на пересечении ключевого столбца и ключевой строки, называется генеральным, и обозначается Xrk

И=min=min=12ключевая строка--Х5

в) Рассчитываем новые значения вектора решений

X?i=Xi--Иik*Xik

Правило1: для ключевой строки новое значение вектора решений не рассчитывается, а просто берется, как значение И.

X?5=И=12 (см.правило1)

X?6=800-12*44=272

X?7=400-12*20=160

г) Определяем новые значения ключевой строки

X?rj=XrjчXrk

Правило 2: каждый столбец, у которого на пересечении с ключевой строкой стоит 0, переписывается без изменений.

Правило 3: в новой симплекс-таблице значения элементов ключевого столбца будут равны 0, а на месте генерального элемента будет стоять 1.

Правило 4: каждая строка, у которой на пересечении с ключевым столбцом стоит 0, переписывается без изменений.

X?51=1 (см.правило 3)

X?52=9 / 10 = 0.9

X?53=4 / 10 = 0.4

X?54=8 / 10 = 0.8

X?55=1 / 10 = 0.1

X?56=0 (см.правило2)

X?57=0 (см.правило2)

д) Находим значения остальных элементов новой симплекс-таблицы:

X?ij=Xij- Xrj*Xik/Xrk

X?61=0 (см.правило2)

X?71=0 (см.правило2)

X?62=

X?72=

X?63=

X?73=

X?64=

X?74=

X?65=

X?75=

X?66=1 (см.правило2)

X?76=0 (см.правило2)

X?67=0 (см.правило2)

X?77=1 (см.правило2)

е) Определяем значения Zj

Zj=

C1=60, C6=0,C7=0

Z1=60*1+0+0=60

Z2=60*0,9+0+0=54

Z3=60*0,4+0+0=24

Z4=60*0,8+0+0=48

Z5=60*0,1+0+0=6

Z6=60*0+0+0=0

Z7=60*0+0+0=0

Таблица15

Z=60*12+0*272+0*160=720

Признак оптимальности нарушен!

2) План2.

а) Ключевой столбец- Х3

б) И=min=min=14,78ключевая строка--Х6

в) Рассчитываем новые значения вектора решений

X?i=Xi--Иik*Xik

X?1=12-14,78*0,4=6,09

X?5=И=14,78 (см.правило1)

X?7=160-14,78*8=41,74

г) Определяем новые значения ключевой строки

X?rj=XrjчXrk

X?61=0 (см.правило 4)

X?62=-11,6 / 18,4 = -0,63

X?63=1 (см. правило 3)

X?64=24,8 / 18,4 = 1,35

X?65=-4,4 / 18,4 = -0,24

X?66=1 / 18,4 = 0,05

X?67=0 (см.правило2)

д) Находим значения остальных элементов новой симплекс-таблицы:

X?ij=Xij- Xrj*Xik/Xrk

X?11=1 (см.правило2)

X?71=0 (см.правило2)

X?12=

X?72=

X?13=0 (см. правило3)

X?73=0 (см. правило3)

X?14=

X?74=

X?15=

X?75=

X?16=

X?76=

X?17=0 (см.правило2)

X?77=1 (см.правило2)

е) Определяем значения Zj

Zj=

C1=60, C3=40,C7=0

Z1=60*1+40*0+0=60

Z2=60*1,15+40*(-0,63)+0=54

Z3=60*0+40*1+0=40

Z4=60*0,26+40*1,35+0=69,6

Z5=60*0,2+40*(-0,24)+0=2,4

Z6=60*(-0,02)+40*0,05+0=0,8

Z7=60*0+40*0+0=0

Таблица16

Z=60*6,09+40*14,78+0*41,74=956,6

Признак оптимальности нарушен!

3) План 3

а) Ключевой столбец - Х2

б) И=min=min=2,8ключевая строка--Х7

в) Рассчитываем новые значения вектора решений

X?i=Xi--Иik*Xik

X?1=6,09-2,8*1,15=6,09

X?=14,78-2,8*(-0,63)=16,54

X?7=И=2,8 (см.правило1)

г) Определяем новые значения ключевой строки

X?rj=Xrj ? Xrk

X?71=0 (см.правило 4)

X?72=1 (см. правило 3)

X?73=0 (см. правило 2)

X?74=5,22 / 15,04 = 0,35

X?75=-0,09 / 15,04 = -0,01

X?76=-0,43 / 15,04 = -0,03

X?77=1 ? 15,04 = 0,07

д) Находим значения остальных элементов новой симплекс-таблицы:

X?ij=Xij- Xrj*Xik/Xrk

X?11=1 (см.правило2)

X?31=0 (см.правило2)

X?12=0 (см.правило3)

X?32=0 (см. правило3)

X?13=0 (см. правило2)

X?33=1 (см. правило2)

X?14=

X?34=

X?15=

X?35=

X?16=

X?36=

X?17=

X?77=

е) Определяем значения Zj

Zj=

C1=60, C3=40,C2=50

Z1=60*1+40*0+50*0=60

Z2=60*0+40*0+5*0=50

Z3=60*0+40*1+5*0=40

Z4=60*(-0,14)+40*1,57+50*0,35=69,6

Z5=60*0,2+40*(-0,24)+50*(-0,01)=1,9

Z6=60*0,01+40*0,04+50*(-0,03)=0,7

Z7=60*(-0,08)+40*0,04+50*0,08=0,8

Таблица16

Данный план оптимален!

Z=60*2,87+40*16,54+50*2,8=973,8

Проверяем ограничения:

X1;X2;X3;X4?0

10*2,87+9*2,8+4*16,54=120

44*2,87+28*2,8+36*16,54=800

20*2,87+28*2,8+16*16,54=400

3. Выводы

3.1 Транспортная задача

В результате вычислений методом потенциалов мы выяснили, что оптимальный план выглядит следующим образом:

Из пункта отправления А1 груз доставляется в пункты назначения: В2- 80т, В5-170т;

Из пункта отправления А2- в пункты назначения: В1-150т; В3-260т; В4-20т; В5-20т;

Из пункта отправления А3- в пункт назначения В4-100т.

Именно таким образом мы достигаем минимального грузооборота, а именно определяем количество груза, перевозимого по маршрутам с наименьшими расстояниями между пунктами.

Данный план допустим, так как удовлетворяет всем ограничениям.

3.2 План выпуска промышленной продукции

В этой задаче мы нашли оптимальный план, при котором мы получим максимум прибыли при ограничении в ресурсах. Выглядит он следующим образом:

Продукция 1- 2,87 единицы

Продукция 2- 2,8 единицы

Продукция 3- 16,54 единицы

Продукция 4 в наш план не входит, ее выпуск нам не выгоден.

Обусловлен такой план соотношением между затратами ресурсов и прибылью на единицу продукции.

Данный план допустим, так как удовлетворяет всем ограничениям.

Список используемой литературы