Максимизирование дохода от выгрузки однородного груза из 80 вагонов

Задача №1

На станции необходимо выгрузить маршрут однородного груза из 80 вагонов. Подаёт, убирает и расставляет вагоны один локомотив, который работает 23 ч в сутки. Из-за различного технического оснащения грузовых фронтов доход от выгрузки одного вагона неодинаков.

Грузовой фронт	Вместимость, вагоны	Затраты локомотиво ч/вагон	Доход ден.ед./вагон
1 2 3	30 40 40	0,2 0,4 0,3	3 5 4

Необходимо: максимизировать доход от выгрузки.

Решение

Обозначим число вагонов, предназначенных для выгрузки на первом грузовом фронте через x₁, на втором – x₂, на третьем – x₃. Тогда целевая функция, выражающая общий доход станции от выгрузки вагонов:

при ограничениях

Составим математическую модель:

где	y1 –	число не поданных под выгрузку вагонов
	y2 –	количество неиспользованных локомотиво·часов
	y3, y4, y5 –	неиспользованные вместимости грузовых фронтов

Построение симплекс таблицы

	x1	x2	x3	y1	y2	y3	y4	y5	решен.	Q
z	-3	-5	-4	0	0	0	0	0	0
y1	1	1	1	1	0	0	0	0	80	80
y2	0,2	0,4	0,3	0	1	0	0	0	23	57,5
y3	1	0	0	0	0	1	0	0	30	-
y4	0	1	0	0	0	0	1	0	40	40
y5	0	0	1	0	0	0	0	1	40	-

Проверяем условие оптимальности. Среди отрицательных элементов z-строки выбираем максимальный по модулю. Это элемент x₂. Следовательно столбец x₂ – ведущий. Проверяем условие допустимости, находим Q. Минимальное значение Q в строке y₄, следовательно y₄ – ведущая строка, а y₂ – исключаемая из базиса переменная.

Для поиска оптимального решения последовательно производим итерации

	x1	x2	x3	y1	y2	y3	y4	y5	решен.	Q
z	-3	0	-4	0	0	0	5	0	200
y1	1	0	1	1	0	0	-1	0	40	40
x2	0,2	0	0,3	0	1	0	-0,4	0	7	70/3
y3	1	0	0	0	0	1	0	0	30	-
y4	0	1	0	0	0	0	1	0	40	-
y5	0	0	1	0	0	0	0	1	40	40

	x1	x2	x3	y1	y2	y3	y4	y5	решен.	Q
z	-1/3	0	0	0	40/3	0	-1/3	0	880/3
y1	1/3	0	0	1	-10/3	0	1/3	0	50/3	50
x2	2/3	0	1	0	10/3	0	-4/3	0	70/3	35
y3	1	0	0	0	0	1	0	0	30	30
x3	0	1	0	0	0	0	1	0	40	-
y5	-2/3	0	0	0	-10/3	0	4/3	1	50/3	-25

	x1	x2	x3	y1	y2	y3	y4	y5	решен.	Q
z	0	0	0	0	40/3	1/3	-1/3	0	910/3
y1	0	0	0	1	-10/3	-1/3	1/3	0	20/3	20
x2	0	0	1	0	10/3	-2/3	-4/3	0	10/3	-2,5
x1	1	0	0	0	0	1	0	0	30	-
x3	0	1	0	0	0	0	1	0	40	40
y5	0	0	0	0	-10/3	2/3	4/3	1	110/3	27,5