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

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

 

Таблица11

П. наз П. отпр	В1	В2	В3	В4	В5	Gi	ai
А1		190 80			180 170
А2	175 50 +		200 260	185 - 120	200 20
А3	230 100 -			200 +
Vj
bj

 

Таблица12

П. наз П. отпр	В1	В2	В3	В4	В5	Gi	ai
А1		190 80			180 170
А2	175 150		200 260	185 20	200 20
А3				200 100
Vj
bj

 

а) Определяем потенциалы пунктов отправления 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+bij Lij+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

в) Xij 0

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. Оптимизация плана выпуска промышленной продукции

 

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

 

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

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

Таблица13

Тип ресурса	Нормы затрат ресурсов на единицу продукции	Запасы ресурсов
Сырье
Рабочее время
Оборудование
Прибыль на единицу продукции

 

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

 

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

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

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

=60X1+50X2+40X3+32X4→max

 

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

;X2;X3;X4≥0

X1+9X2+4X3+8X4≤120

X1+28X2+36X3+60X4≤800

X1+28X2+16X3+32X4≤400

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

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

Так как в ограничениях нашей задачи левая часть меньше или равна правой, то неравенства мы преобразуем в равенства (кроме первого) путем добавления свободных переменных, коэффициент которых равен 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

Cj
Ci	Базис	P0	X1	X2	X3	X4	X5	X6	X7
	X5
	X6
	X7
Zj
Zj-Cj	-60	-50	-40	-32

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

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

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

1) План 1

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

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

 

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

 

Θ=min , Xik >0

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

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

 

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

 

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

′i=Xi-Θik*Xik

 

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

X′5=Θ=12 (см.правило1)′6=800-12*44=272′7=400-12*20=160

 

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

′rj=Xrj÷Xrk

 

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

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

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

′51=1 (см.правило 3)′52=9 / 10 = 0.9′53=4 / 10 = 0.4′54=8 / 10 = 0.8′55=1 / 10 = 0.1′56=0 (см.правило2)′57=0 (см.правило2)

 

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

 

X′ij=Xij- Xrj*Xik/Xrk′61=0 (см.правило2)′71=0 (см.правило2)

X′62=′72=′63=′73=′64=′74=′65= ′75=′66=1 (см.правило2)′76=0 (см.правило2)′67=0 (см.правило2)′77=1 (см.правило2)

 

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

 

Zj= =60, C6=0,C7=0=60*1+0+0=60=60*0,9+0+0=54=60*0,4+0+0=24=60*0,8+0+0=48=60*0,1+0+0=6=60*0+0+0=0=60*0+0+0=0

 

Таблица15

Cj
Ci	Базис	P0	X1	X2	X3	X4	X5	X6	X7
	X1			0,9	0,4	0,8	0,1
	X6			-4,6	18,4	24,8	-4,4
	X7						-2
Zj
Zj-Cj			-16

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

 

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

) План2.

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

 

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

 

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

 

X′i=Xi-Θik*Xik′1=12-14,78*0,4=6,09

X′5=Θ=14,78 (см.правило1)′7=160-14,78*8=41,74

 

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

′rj=Xrj÷Xrk′61=0 (см.правило 4)′62=-11,6 / 18,4 = -0,63′63=1 (см. правило 3)′64=24,8 / 18,4 = 1,35′65=-4,4 / 18,4 = -0,24′66=1 / 18,4 = 0,05′67=0 (см.правило2)

 

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

 

X′ij=Xij- Xrj*Xik/Xrk′11=1 (см.правило2)′71=0 (см.правило2)

X′12=′72=′13=0 (см. правило3)′73=0 (см. правило3)′14=′74=′15=′75=′16=′76=′17=0 (см.правило2)′77=1 (см.правило2)

 

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

 

Zj= =60, C3=40,C7=0=60*1+40*0+0=60=60*1,15+40*(-0,63)+0=54=60*0+40*1+0=40=60*0,26+40*1,35+0=69,6=60*0,2+40*(-0,24)+0=2,4=60*(-0,02)+40*0,05+0=0,8=60*0+40*0+0=0

 

Таблица16

Cj
Ci	Базис	P0	X1	X2	X3	X4	X5	X6	X7
	X1	6,09		1,15		0,26	0,2	-0,02
	X3	14,78		-0,63		1,35	-0,24	0,05
	X7	41,74		15,04		5,22	-0,09	-0,43
Zj		43,8		69,6	2,4	0,8
Zj-Cj		-6,2		37,6	2,4	0,8

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

 

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

) План 3

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

 

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

 

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

 

X′i=Xi-Θik*Xik′1=6,09-2,8*1,15=6,09

X′=14,78-2,8*(-0,63)=16,54′7=Θ=2,8 (см.правило1)

 

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

′rj=Xrj ∕ Xrk′71=0 (см.правило 4)′72=1 (см. правило 3)′73=0 (см. правило 2)′74=5,22 / 15,04 = 0,35′75=-0,09 / 15,04 = -0,01′76=-0,43 / 15,04 = -0,03′77=1 ∕ 15,04 = 0,07

 

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

 

X′ij=Xij- Xrj*Xik/Xrk′11=1 (см.правило2)′31=0 (см.правило2)′12=0 (см.правило3)′32=0 (см. правило3)′13=0 (см. правило2)′33=1 (см. правило2)

X′14=′34=′15=′35=′16=′36=′17=′77=

 

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

 

Zj= =60, C3=40,C2=50=60*1+40*0+50*0=60=60*0+40*0+5*0=50=60*0+40*1+5*0=40=60*(-0,14)+40*1,57+50*0,35=69,6=60*0,2+40*(-0,24)+50*(-0,01)=1,9=60*0,01+40*0,04+50*(-0,03)=0,7=60*(-0,08)+40*0,04+50*0,08=0,8

 

Таблица16

Cj
Ci	Базис	P0	X1	X2	X3	X4	X5	X6	X7
	X1	2,87				-0,14	0,2	0,01	-0,08
	X3	16,54				1,57	-0,24	0,04	0,04
	X2	2,8				0,35	-0,01	-0,03	0,07
Zj				71,9	1,9	0,7	0,8
Zj-Cj				39,9	1,9	0,7	0,8

 

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

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

 

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

;X2;X3;X4≥0

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

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

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

 

Выводы

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

 

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

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

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

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

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

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

 

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

 

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

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

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

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

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

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

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

 

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

 

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

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