Содержание

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

Формирование схемы движения. Транспортная задача

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

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

3. Симплекс-метод

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

Формирование схемы движения (Транспортная задача)

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

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

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

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

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

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

Задание №22

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

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

Пункты отправления	Объем ввоза, тыс. тонн
А	50
Г	100
Е	350

Пункты назначения	Объем ввоза, тыс. тонн
К	70
Л	130
М	50
Н	150
П	100

Расстояния между пунктами, км:

А-К	350	Г-К	220	Е-К	200
А-Л	400	Г-Л	290	Е-Л	240
А-М	340	Г-М	160	Е-М	235
А-Н	230	Г-Н	260	Е-Н	150
А-П	180	Г-П	255	Е-П	225

Используя метод северо-западного угла, составляем первоначальный план перевозок и проверяем на оптимальность:

Bj	К=70		Л=130		М=50		Н=150		П=100		Ui
Ai
А=50	50	350	-	400	-	340	-	230	-	180	405
Г=100	20	220	80	290	-	160	-	260	-	255	275
Е=350	-	200	50	240	50	235	150	150	100	225	225
Vj	-55		15		10		-75		0

Определяются потенциальные оценки свободных клеток:

12=	20		23=	125
13=	75		24=	-60
14=	100		25=	55
15=	225		31=	-30

План перевозок не оптимален, поскольку имеются положительные потенциальные оценки, а значение целевой функции:

Z=50*350+20*220+80*290+50*240+50*235+150*150+100*225=113850

Может быть улучшено.

Выбираем цикл с включением в качестве вершины клетки с потенциальной оценкой +125, что позволяет перераспределить перевозки:

80	80		-	30	80		50
130			50	130			50
50	100		50	100	100		-

и получить новый план перевозок в виде очередной таблице:

Bj	К=70		Л=130		М=50		Н=150		П=100		Ui
Ai
А=50	50	350	-	400	-	340	-	230	-	180	405
Г=100	20	220	30	290	50	160	-	260	-	255	275
Е=350	-	200	100	240	-	235	150	150	100	225	225
Vj	-55		15		-115		-75		0

Полученный план так же не оптимален, так как среди потенциальных оценок свободных клеток есть положительные:

12=	20		24=	-60
13=	-50		25=	55
14=	100		31=	-30
15=	225		33=	-125

При этом значение целевой функции:

Z=50*350+20*220+30*290+100*240+50*160+150*150+100*225=107600

Улучшилось.

Снова выбираем цикл с включением в качестве вершины клетки с потенциальной оценкой +20, что позволяет перераспределить перевозки:

50	50		-	20	50		30
70			30	70			30
20	50		30	50	50		-

и получить новый план перевозок в виде очередной таблице:

Bj	К=70		Л=130		М=50		Н=150		П=100		Ui
Ai
А=50	20	350	30	400	-	340	-	230	-	180	385
Г=100	50	220	-	290	50	160	-	260	-	255	255
Е=350	-	200	100	240	-	235	150	150	100	225	225
Vj	-35		15		-95		-75		0

Полученный план так же не оптимален, так как среди потенциальных оценок свободных клеток есть положительные:

13=	-50		24=	-60
14=	80		25=	55
15=	205		31=	-30
22=	-20		33=	-125

При этом значение целевой функции:

Z=20*350+50*220+30*400+100*240+50*160+150*150+100*225=107000

Улучшилось.

Снова выбираем цикл с включением в качестве вершины клетки с потенциальной оценкой +80, что позволяет перераспределить перевозки:

30	30		-	-	30		30
130			150	130			150
100	250		150	130	250		120

и получить новый план перевозок в виде очередной таблице:

Bj	К=70		Л=130		М=50		Н=150		П=100		Ui
Ai
А=50	20	350	-	400	-	340	30	230	-	180	305
Г=100	50	220	-	290	50	160	-	260	-	255	175
Е=350	-	200	130	240	-	235	120	150	100	225	225
Vj	45		15		-15		-75		0

Полученный план так же не оптимален, так как среди потенциальных оценок свободных клеток есть положительные:

12=	-80		24=	-160
13=	-50		25=	-80
15=	125		31=	70
22=	-100		33=	-25

При этом значение целевой функции:

Z=20*350+50*220+130*240+50*160+30*230+120*150+100*225=104600

Улучшилось.

Снова выбираем цикл с включением в качестве вершины клетки с потенциальной оценкой +125, что позволяет перераспределить перевозки:

30	30		-	-	30		30
150			100	150			100
120	220		100	150	220		70

и получить новый план перевозок в виде очередной таблице:

Bj	К=70		Л=130		М=50		Н=150		П=100		Ui
Ai
А=50	20	350	-	400	-	340	-	230	30	180	180
Г=100	50	220	-	290	50	160	-	260	-	255	50
Е=350	-	200	130	240	-	235	150	150	70	225	225
Vj	170		15		110		-75		0

Полученный план так же не оптимален, так как среди потенциальных оценок свободных клеток есть положительные:

12=	-205		24=	-285
13=	-50		25=	-205
14=	-125		31=	195
22=	-225		33=	100

При этом значение целевой функции:

Z=20*350+50*220+130*240+50*160+150*150+30*180+70*225=100850

Улучшилось.

Снова выбираем цикл с включением в качестве вершины клетки с потенциальной оценкой +195, что позволяет перераспределить перевозки:

20	50		30	-	50		50
20			100	20			100
-	70		70	20	70		50

и получить новый план перевозок в виде очередной таблице:

Bj	К=70		Л=130		М=50		Н=150		П=100		Ui
Ai
А=50	-	350	-	400	-	340	-	230	50	180	180
Г=100	50	220	-	290	50	160	-	260	-	255	245
Е=350	20	200	130	240	-	235	150	150	50	225	225
Vj	-25		15		-85		-75		0

11=	-195		22=	-30
12=	-205		24=	-90
13=	-245		25=	-10
14=	-125		33=	-95

Z=50*220+20*200+130*240+50*160+150*150+50*180+50*225=96950

Таким образом, получен оптимальный план перевозок.

Симплекс-метод

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

Тип ресурса	Нормы затрат ресурсов на единицу продукции				Запасы ресурсов
	1	2	3	4
Сырье	6	4	3	5	70
Рабочее время	23	15	19	31	450
Оборудование	11	15	8	17	140
Прибыль на единицу продукции	31	26	9	17

На основе исходных данных составляется математическая модель задачи:

Для решения задачи симплекс-методом необходимы очевидные промежуточные преобразования:

Если выбрать в качестве базисных переменных введенные дополнительные переменные , , то последняя модель переписывается в виде:

В итоге формируется симплекс-таблица следующего вида:

П БП					1
	6	4	3	5	70
	23	15	19	31	450
	11	15	8	17	140
	-31	-26	-9	-17	0

Решение не оптимально. В строке Z присутствуют отрицательные коэффициенты. Выбираем разрешающий столбец с максимальным отрицательным значением . Для выбора разрешающе строки свободные коэффициенты (70, 450, 140) делят на элементы разрешающего столбца. По минимальному положительному отношению выбирается разрешающая строка . Пересечение разрешающего столбца и строка дает разрешающий инструмент (=6)

БП/П	(-Х1)	(-Х2)	(-Х3)	(-Х4)	1
Х5=	6	4	3	5	70	11,6
Х6=	23	15	19	31	450	19,56
Х7=	11	15	8	17	140	12,72
Z=	-31	-26	-9	-17	0

При выборе разрешающими столбца и строки Х5 получаем новую симплекс-таблицу:

БП/П	(-Х5)	(-Х2)	(-Х3)	(-Х4)	1
Х1=	0,16	0,66	0,5	0,83	11,66	17,66
Х6=	-3,83	-0,33	7,5	11,83	181,66	-550,48
Х7=	-1,83	7,66	2,5	7,83	11,66	1,52
Z=	5,16	-5,33	6,5	8,83	361,66

БП/П	(-Х5)	(-Х7)	(-Х3)	(-Х4)	1
Х1=	0,32	-0,08	0,28	0,152	10,65
Х6=	-3,91	0,04	7,6	12,17	182,17
Х2=	-0,23	0,13	0,32	1,02	1,52
Z=	3,89	0,69	8,23	14,28	369,78

Согласно полученным данным оптимальным является распределение заказа между 10,65 станками первого типа и 182,17 станками шестого типа. При минимальных издержках в 369,78 ден. единиц.

14