Лабораторная работа №4

Задача 4.14: В 4 пункта назначения доставляется однородный груз 150, 200, 250 и 300 т при этом используется 3 виды подвижного состава: 13 вагонов грузоподъемностью 62 т, 6 автомобилей – 12 т, 5 автомобилей – 7 т. Заданы стоимости доставки единицы груза каждым видом подвижного состава в каждый пункт назначения:

	Вагон	Авто 12т	Авто 7т
i	1	2	3
Кол-во ПС	13	6	5
Грузоподъем.	62	12	7
Себестоимость	35	8	5

Выбрать такое распределение груза по видам подвижного состава, чтобы все грузы были доставлены, а общая стоимость перевозки была минимальна. Выписать целевую функцию и ограничения. Определить суммарную стоимость работ.

Решение

Переменные для описания задачи:

I = 3 – количество видов подвижного состава;

J = 4 – количество пунктов назначения;

– количество единиц подвижного состава i-го типа, т, i = 1…3;

- грузоподъемность 1 единицы подвижного состава i-го типа, т, i = 1…3;

– заявка на груз j-го типа, т, j=1…4;

– стоимость рейса i-го типа подвижного состава, ден.ед., i=1…3;

– количество единиц подвижного состава i-го типа, доставляющие груз в j-ый пункт назначения, ед., i=1…3, j=1…4.

Значение переменных , , заданы и входят в состав исходных данных; проектные переменные определяется в ходе решения задачи линейного программирования.

Целевая функция (суммарный грузооборот) записывается следующим образом:

(4.1)

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

(4.2)

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

1. суммарное количество груза, доставляемого в j-ый пункт назначения, всеми видами подвижного состава, должно быть не меньше заявки этого пункта:

, j = 1…4; (4.3)

2. суммарное количество единиц подвижного состава i-го типа, доставляющего груз во все пункты назначения, должно быть меньше общего количество единиц подвижного состава этого типа:

, i = 1…3. (4.4)

Сформулированная задача является многопараметрической задачей линейного программирования минимизации критерия (4.1) с учетом выполнения условия (4.2) и ограничений (4.3) и (4.4).

Проверим выполнение условия (4.2) решения задачи.

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

Суммарной количество груза, которое должно быть доставлено всеми типами подвижного состава:

Условие (4.2) выполняется: суммарное количество груза, которое может быть доставлено, превышает суммарное количество груза, которое необходимо доставить на 913 – 900 = 13 т.

Целевая функция (4.1) записывается следующим образом:

Ограничения (4.3) на доставку груза в пункты назначения записывается следующим образом:

Ограничения (4.4) на суммарное количество единиц подвижного состава, доставляющего груз во все пункты назначения, записывается следующим образом:

;

;

.

Решение задачи целочисленного линейного программирования осуществляется с использованием средства “Поиска решения” пакета MS Excel методом “ветвей и границ”.

Значение переменных * (т), полученные в результате решения задачи, приведены в таблице.

Xi/j*Pi		Подвижной состав
		1	2	3
Пункты назначения	1	124	12	14
	2	186	0	14
	3	186	60	7
	4	310	0	0

Значение целевой функции составило 528 ден.ед.

В первый пункт назначения груз доставляется первым типом подвижного состава (124т.), вторым типом (12т.), третьим типом (14т.), во второй пункт – первым типом (186т.), третьим типом (14т.), в третий пункт – первым типом (186т.), вторым типом (60т.), третьим типом (7т.), в четвертый пункт – первым типом (310 т.).