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

1. Оптимизация доставки грузов

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

1.2 Формирование схемы движения

1.2.1 Составление начального плана перевозок

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

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

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

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

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

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

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

2.3 Решение задачи симплекс методом

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

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

3. Выводы

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

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

1. Сущность оптимизации доставки грузов

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

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

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

Таблица 1

Таблица 2

Таблица 3

1.2 Формирование схемы движения

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

Целевая функция:

Гдерасстояние между i-м пунктом отправления и j-м пунктом назначения (км);

— объем перевозок между i-м пунктом отправления Ограничения:

=

Гдеобъем отправления из i-го пункта

— объем потребления в j-ом пункте

iиндекс пункта отправления (i=1,…, m)

jиндекс пункта назначения (j=1,…, n)

mчисло пунктов отправления

nчисло пунктов назначения

1.2.1 Составление начального плана перевозок

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

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

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

;; и т. д.

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

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

Таблица4.

F=L11×11+ L12×12+ L12×12+ L13×13+ L14×14+ L15×15+ L21×21+ L22×22+ L23×23+ L24×24+L25×25+ L31×31+ L32×32+ L33×33+ L34×34 + L35×35 =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=182 200

а) Определяем потенциалы пунктов отправления 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=L11×11+ L12×12+ L12×12+ L13×13+ L14×14+ L15×15+ L21×21+ L22×22+ L23×23+ L24×24+L25×25+ L31×31+ L32×32+ L33×33+ L34×34 + L35×35 =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=180 000

а) Определяем потенциалы пунктов отправления 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=L11×11+ L12×12+ L12×12+ L13×13+ L14×14+ L15×15+ L21×21+ L22×22+ L23×23+ L24×24+L25×25+ L31×31+ L32×32+ L33×33+ L34×34 + L35×35 =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=161 500

а) Определяем потенциалы пунктов отправления 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=L11×11+ L12×12+ L12×12+ L13×13+ L14×14+ L15×15+ L21×21+ L22×22+ L23×23+ L24×24+L25×25+ L31×31+ L32×32+ L33×33+ L34×34 + L35×35 =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=155 750

а) Определяем потенциалы пунктов отправления 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=L11×11+ L12×12+ L12×12+ L13×13+ L14×14+ L15×15+ L21×21+ L22×22+ L23×23+ L24×24+L25×25+ L31×31+ L32×32+ L33×33+ L34×34 + L35×35 =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=151 750

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

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

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

груз экономический математический прибыль Таблица13

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

Искомая переменная:

Х-количество выпускаемой продукции Целевая функция:

Z=60X1+50X2+40X3+32X4>max

Ограничения:

X1;X2;X3;X4?0

10X1+9X2+4X3+8X4?120

44X1+28X2+36X3+60X4?800

20X1+28X2+16X3+32X4?400

2.3 Решение задачи симплекс методом

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=XijXrj*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=XijXrj*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=XijXrj*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 в наш план не входит, ее выпуск нам не выгоден.

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

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

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

1. Бережная Е. В., Бережной В. И. Математические методы моделирования экономических систем. 2001.

2. Бабурин В. А, Бабурин Н. В. Управление грузовыми перевозками на водном транспорте. 2007