Моделирование производственных и экономических процессов

 

 

 

 

Вывод: Таким образом, целевая функция получает  максимальное значение при  x₁ = 2 и x₂ =1,75и f = 4*2+5*1,75 = 18,5.

 

 

 

 

 

 

 

 

 

2.3 Алгоритм решения задачи симплексным методом

 

1. Перевести неравенство в равенство путем введения новых переменных;
2. Исходную расширенную систему занести в первую симплексную таблицу. В первый столбец таблицы занести основные переменные (базис), во втором столбце таблицы записываются свободные члены системы, далее идут столбцы, в которые вносятся все переменные. В последний столбец записываются оценочные отношения ( ). В последней строке указываются коэффициенты целевой функции с противоположным знаком.
3. Проверяется выполнение критерия оптимальности при решении задачи на max (наличие в последней строке отрицательных коэффициентов). Если таких коэффициентов нет, то решение оптимально.
4. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный элемент в последней строке определяет разрешающий столбец.
5. При составлении оценочных ограничений в каждой строке необходимо пользоваться следующими правилами: 

а) если знаки свободного члена и коэффициентов при  переменных имеют разные знаки, то ;

б)если свободные члены  равны 0, а коэффициенты при переменной отрицательные, то ;

в) если коэффициент при  переменной равен 0, то ;

г) если свободный член равен 0, а коэффициент при переменной > 0, то ;

6. Найти  min , которая определяет разрешающую строку;
7. На пересечении разрешающей строки и столбца найти разрешающий элемент;
8. Перейти к следующей таблице по правилам:

а) в левом столбце  записывается новый базис, вместо основной переменной новую переменную;

б) в столбцах, соответствующих  основным переменным, проставляются 0 и 1, 1– напротив своей переменной, 0 – напротив чужой;

в) новая строка получается из старой, путем деления на разрешающий  элемент;

г) остальные элементы вычисляются по правилу метода Гаусса;

д) далее перейти к  следующей итерации.

 

 

 

 

 

 

 

 

 

Глава III

 

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

 

Метод северо-западного  угла

 

Bj Ai	210	190	220	180
140	4 140	5	6	1
140	0 70	3	2	1
520	2	4 120	7 220	8 180

 

F = 140*4+70*0+70*3+4*120+7*220+8*180=4230

 

Метод минимального элемента по столбцу

Bj Ai	210	190	220	180
140	4	5	6	1
140	0 140	3	2	1
520	2 70	4 190	7 80	8 180

 

F = 140*0+70*2+190*4+140*6+80*7+180*8=3740

 

Метод минимального элемента по строке

Bj Ai	200	200	100	300
140	0 190	1	12	9
140	4	7 200	14	11
520	3 10	10	2 100	8 300

 

F = 180+760+220+1540=2700

Метод минимального элемента

Bj Ai	210	190	220	180
140	0 190	5	6	1 140
140	4	3	2	1 40
520	2 110	4 190	7 220	8

 

F = 190*0 + 200*7 + 80*0 + 10*3 + 100*2 + 300*8 = 4030

 

Метод потенциалов

Bj Ai	V1=5	V2=-3	V3=0	V4=1
U1=0	4	5	6	1 140
U2=3	0	3 200	2 140	1
U3=-7	2 210	4 150	7 80	8 40

 

 

δ₁₁ = -5-0-4=-9<0  

δ₁₂ = -3-5=-8<0

δ₁₃ =-6=0<0

δ₂₁ =-5+2=-3<0

δ₂₂ =-3+2-3=-4<0

δ₂₄ =3-1=2

 

 

Вывод: Таким образом, целевая функция получает  максимальное значение при  x₁ = 2 и x₂ =1,75и f = 4*2+5*1,75 = 18,5.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. 2 Алгоритм решения транспортной задачи.

 

Важным частным случаем  задачи линейного программирования является транспортная задача.

Постановка задачи: Пусть имеется m поставщиков и n  потребителей. Мощность поставщиков и спросы потребителей, а так же затраты на перевозку груза для каждой пары «поставщик – потребитель» заданы таблицей.

поставщики	потребители	В1	В2	…	Вj	…	Bn	Мощность поставщиков
A1		С11	С12		С1j		С1n	a1
A2		С21	С22		С2j		С2n	a2
…		…	…		…		…
Ai		Сij	Сij		Сij		Сin	ai
…		…	…		…		…
Am		Cm1	Cm2		Cmj		Cmn	am
Спрос потребителей		b1	b2		bj		bn

Найти объемы перевозок каждой пары «поставщик – потребитель» так, чтобы: мощности всех поставщиков были реализованы; спросы всех потребителей были удовлетворены; суммарные затраты на перевозку были бы максимальны.

Особенности математической модели транспортной задачи:

• система ограничений есть система уравнений, то есть задача ЛП в каноническом виде;
• коэффициенты при неизвестных системы ограничений равны единицы или нулю;
• каждая переменная входит в систему ограничений два раза: один раз в систему ограничений поставок, второй раз – в систему ограничений спроса.

 

Математическая модель транспортной задачи.

 

Пусть хij – количество груза, перевозимого с i-го в j-й пункт.

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

Система ограничений:

 

Для решения задачи составляется таблица. В клетки таблицы записывается стоимость соответствующих перевозок сij и в них же заносятся значения перевозок xij, удовлетворяющих поставленным ограничениям. Клетки с не нулевыми перевозками называются базисными, а с нулевыми – свободными. В зависимости от соотношения между запасами и заявками транспортная задача называется сбалансированной или несбалансированной.

Сбалансированная ТЗ:

Несбалансированная ТЗ:

Для сбалансированной ТЗ ограничения принимают вид равенств, то есть получаем m+n ограничений, в которых все переменные линейно зависимы. В результате допустимое решение сбалансированной ТЗ может быть получено, если заполнять клетки транспортной таблицы таким образом, чтобы сумма перевозок в каждой строке должна быть равна запасам ai, а сумма перевозок в каждом столбце равна соответствующей заявке вj. Вариантов заполнения транспортной таблицы множество, поэтому искомым решением является то из допустимых решений, для которых общая стоимость перевозок будет минимальной.

 

Методы решения транспортной задачи.

 

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

МЕТОД СЕВЕРО-ЗАПАДНОГО  УГЛА.  Заполнение клеток происходит последовательно по следующему алгоритму: сначала вывозится груз из пункта А1 и завозится в пункт В1, и этой перевозке х11 присваивается максимально возможное значение. Если заявка пункта В1 выполнена, а в пункте А1 еще остается груз, то он вывозится в пункт В2 и т.д.  Если в пункте А1 недостаточно было груза для В1, то недостающий груз берется из А2 и т.д.

После того как спрос  потребителя  А1 удовлетворен, он выпадает из рассмотрения и т.д.

 

	В1	В2	В3	В4	Запасы
А1	15                        5	5                          7	6	8	20
А2	6	25                        7	8	5	25
А3	5	5                          4	25                        6	7	30
А4	6	5	10                        7	5                          4	15
А5	5	6	6	10                        6	10
Заявки	15	35	35	15	100

Стоимость перевозки: W=5*15+5*7+25*7+5*4+25*6+10*7+5*4+10*6=605

Существенным недостатком  метода северо-западного угла является то, что он построен без учета  стоимости перевозок.

МЕТОД МИНИМАЛЬНОГО ЭЛЕМЕНТА. Заполнение клеток транспортной таблицы  начинается с той клетки, в которой значение минимально. В нее записывается максимально возможное значение перевозки хij, которое может быть равно либо запасу аi, либо заявке вj. Если заявка вj выполнена полностью, то j-й столбец больше не рассматривается. Если не вывезенный груз еще остался, то он вывозится в пункт с наименьшим тарифом.

 

	В1	В2	В3	В4	Запасы
А1	15                        5	7	5                          6	8	20
А2	6	7	25                        8	5	25
А3	5	30                        4	6	7	30
А4	6	5	7	15                        4	15
А5	5	5                          6	5                          6	6	10
Заявки	15	35	35	15	100

Стоимость перевозки: W = 30*4+5*6+15*4+15*5+5*6+25*8+5*6 = 545.

РАСПЕРЕДЕЛЕННЫЙ МЕТОД  УЛУЧШЕНИЯ ПЛАНА ПЕРЕВОЗОК. Для  улучшения плана используют цикл транспортной таблицы. Цикл – это несколько клеток, соединенных замкнутой ломанной с прямыми углами.

Изобразим два цикла: А1В1, А1В2, А2В2, А2В1; А1В3,А1В4, А2В4, А2В6, А1В5, А4В5, А4В3.

поставщики	потребители	В1	В2	В3	В4	В5	B6	Мощность поставщиков
A1		С11	С12	С13	С14	С15	С16	a1
A2		С21	С22	С23	С24	С25	С26	a2
A3		С31	С32	С33	С34	С35	С36	a3
А4		С41	С42	С43	С44	С45	С46	а4
A5		С51	С52	С53	С54	С55	С56	a5
Спрос потребителей		b1	b2	в3	b4	в5	b6