С железнодорожной станции ежедневно отправляются скорые и пассажирские поезда

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

Вагоны

плацкартные купейные мягкие
Скорый поезд 4 7 4
Пассажирский поезд 6 4 2
Число пассажиров 58 40 32
Парк вагонов 80 70 20

Решение.

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

Введем следующие переменные:
х1- количество скорых поездов;
x2 – количество пассажирских поездов.

Чиcло перевозимых пассажиров:
z=a1∙х1+a2∙x2,
где a1 и a2 – вместимость скорого и пассажирского поездов.
По условию задачи:
a1=4∙58+7∙40+4∙32=640
a2=6∙58+4∙40+2∙32=572
Целью задачи является определение среди всех допустимых значений x1, х2 таких, которые максимизируют число перевозимых пассажиров, т. е. целевую функцию z=640∙х1+572∙x2.
Перейдем к ограничениям, которые налагаются на x1, х2.
Количество поездов не может быть отрицательным, следовательно: x1, x2≥0.
Ограничение по парку плацкартных вагонов:
4×1+6×2≤80
Ограничение по парку купейных вагонов:
7×1+4×2≤70
Ограничение по парку мягких вагонов:
4×1+2×2≤20
Ограничение на пропускную способность дороги – не более шести пассажирских поездов в день: x2≤6.
Таким образом, математическая модель данной задачи имеет следующий вид:
z=640∙х1+572∙x2→ max
4×1+6×2≤80 7×1+4×2≤704×1+2×2≤20×2≤6×1, x2≥0

Решим задачу графическим методом.
Построим область допустимых решений, т.е. решим графически систему неравенств.
Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами:
4×1+6×2≤80 7×1+4×2≤704×1+2×2≤20×2≤6×1, x2≥0
Границей неравенства 4×1+6×2≤80 является прямая4×1+6×2=80, построим ее по двум точкам:

Х1 0 20
Х2 13,(3) 0

Произвольная точка (0; 0) удовлетворяет неравенству 4×1+6×2≤80, поэтому областью решения неравенства является область, в которой находится точка (0; 0). Полуплоскость решения обозначена стрелкой.
Границей неравенства 7×1+4×2≤70 является прямая7×1+4×2=70, построим ее по двум точкам:

Х1 0 10
Х2 17,5 0

Произвольная точка (0; 0) удовлетворяет неравенству 7×1+4×2≤70, поэтому областью решения неравенства является область, в которой находится точка (0; 0). Полуплоскость решения обозначена стрелкой.
Границей неравенства 4×1+2×2≤20 является прямая4×1+2×2=20, построим ее по двум точкам:

Х1 0 5
Х2 10 0

Произвольная точка (0; 0) удовлетворяет неравенству 4×1+2×2≤20, поэтому областью решения неравенства является область, в которой находится точка (0; 0). Полуплоскость решения обозначена стрелкой.
Неравенство x2≤6 определяет полуплоскость, лежащую ниже прямой x2=6, параллельной оси абсцисс. Полуплоскость решения обозначена стрелкой.
Пересечением полуплоскостей будет являться область, координаты точек которой удовлетворяют условию неравенств системы ограничений задачи. Не забудем про ограничения x1, x2≥0: условия неотрицательности переменных ограничивают область допустимых решений первым квадрантом. Имеем многоугольник решений ОАВС:

Рассмотрим целевую функцию задачи:
z=640∙х1+572∙x2→ max.
Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление возрастания функции Z(X). Начало вектора – точка (0; 0), конец – точка (640; 572). Для удобства построения вектора- градиента, построим вектор, сонаправленный с {640, 572}, который “удобно” изобразить в масштабе построенного изображения, пусть это будет вектор {640/320, 572/320}={2, 1,7875}.
Строим прямую 2х1+1,7875×2= const – линию уровня функции Z(X), перпендикулярную вектору-градиенту. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта “зеленая” прямая. Она пересекает область в точке В, которая получена в результате пересечения прямых
4×1+2×2=20 и x2=6.
Тогда ее координаты удовлетворяют уравнениям этих прямых.
Составим систему уравнений:
4×1+2×2=20 ,x2=6.
Итак, x2=6,×1=20-12:4=2.
Таким образом, максимальное значение целевой функции:
z=640∙2+572∙6=4712

Итак, x1=2, x2=6, zmax=4712

Решим задачу симплекс-методом.
Приведем задачу

z=640∙х1+572∙x2→ max
4×1+6×2≤80 7×1+4×2≤704×1+2×2≤20×2≤6×1, x2≥0
к канонической форме. Для этого от системы неравенств перейдем к системе линейных уравнений, введя дополнительные переменные х3, x4, x5, х6 и перепишем условие задачи:
z=640∙х1+572∙x2→ max
4×1+6×2+x3=80 7×1+4×2+x4=704×1+2×2+x5=20×2+x6=6×1, x2,x3,x4,x5,x6≥0

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A=4610008074010070402100001001206

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3,x4,x5,x6. Полагая, что свободные переменные равны 0, получим первый опорный план:
X = (0,0,0, 80, 70, 20, 6)

Базисное решение называется допустимым, если оно неотрицательно.
Составим симплекс-таблицу:

Первая симплекс-таблица
Базис Свободные члены Свободные переменные

X1 X2 X3 X4 X5 X6
X3 80 4 6 1 0 0 0
X4 70 7 4 0 1 0 0
X5 20 4 2 0 0 1 0
X6 6 0 1 0 0 0 1
Индексная строка 0 -640 -570 0 0 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ключевого выберем столбец, соответствующий переменной x1 (при отыскании максимума выбирается наименьший отрицательный элемент в индексной строке – это -640).
Компоненты вектора свободных членов делятся на положительные элементы ключевого столбца и из них выбирается наименьшее.
Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:
min (80:4 , 70:7,20:4) = min (20, 10, 5)=5
Следовательно, третья строка является ведущей.
Разрешающий элемент равен 4, он находится на пересечении ключевого столбца и ключевой строки.
Вместо переменной x5 в план войдет переменная x1.
Каждый элемент ключевой строки делится на разрешающий элемент. Полученные частные являются элементами ключевой строки следующей таблицы.
Ключевой столбец в новой таблице – нули, за исключением разрешающего элемента.
Остальные элементы рассчитываются по схеме (выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент):
Эн = ЭС – (Э1х Э2)/ ЭР
Эн – новый элемент, ЭС – старый элемент, Э1 – элемент ключевой строки, Э2 – элемент ключевого столбца, ЭР – разрешающий элемент.
Получаем новую симплекс-таблицу:
Вторая симплекс-таблица
Базис Свободные члены Свободные переменные

X1 X2 X3 X4 X5 X6
X3 60 0 4 1 0 -1 0
X4 35 0 0,5 0 1 -1,75 0
X1 5 1 0,5 0 0 0,25 0
X6 6 0 1 0 0 0 1
Индексная строка 3200 0 -252 0 0 160 0
В столбце свободных членов все элементы положительны, то полученное решение является допустимым.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ключевого выберем столбец, соответствующий переменной x2 (наименьший отрицательный элемент в индексной строке – это -252). Компоненты вектора свободных членов делим на положительные элементы ключевого столбца и из них выбираем наименьшее:
min (60:4 , 35:0.5,5:0.5,6:1) = min (15,70,10,6)=6
Следовательно, четвертая строка является ведущей.
Разрешающий элемент равен 1, он находится на пересечении ключевого столбца и ключевой строки.
Вместо переменной x6 в план войдет переменная x2.
Получаем новую симплекс-таблицу:
Третья симплекс-таблица
Базис Свободные члены Свободные переменные

X1 X2 X3 X4 X5 X6
X3 36 0 0 1 0 -1 -4
X4 32 0 0 0 1 -1,75 -0,5
X1 2 1 0 0 0 0,25 -0,5
X2 6 0 1 0 0 0 1
Индексная строка 4712 0 0 0 0 160 252

Среди значений индексной строки нет отрицательных. Поэтому таблица определяет оптимальный план задачи. Т.е. полученное решение максимизирует целевую функцию. При этом оптимальным планом будут величины:
х1=2, х2=6 (они свободные), x3=36, x4 = 32 (они базисные), целевая функция:
z=640∙х1+572∙x2=640∙2+572∙6=4712

Значение базисной переменной х3=36 означает, что есть резерв плацкартных вагонов в количестве 36 штук, что свидетельствует об их излишках. Значение базисной переменной х4=32 означает, что есть резерв купейных вагонов в количестве 32 штук, что свидетельствует об их излишках.

Решим задачу с помощью MS Excel.
На рабочем листе введем числовые данные задачи. Для оптимального решения, которое появится после вычислений, отведены ячейки B9:В10. Ячейка В12 зарезервирована для вычисления значения целевой функции, ячейки F3:F6 – для левых частей ограничений.
В режиме отображения формул заполненная таблица имеет вид:

Поскольку ячейки оптимального решения B9:В10 не содержат данных, значение расхода сырья и целевой функции пока 0.
Выбираем команду «Поиск решения» и в появившееся диалоговое окно вводим данные, при этом ограничения удобнее задавать в виде диапазонов:

Нажимаем ОК, затем “Выполнить”. После нажатия кнопки «Выполнить» открывается окно «Результаты поиска решения», которое сообщает, что решение найдено. Сохраняем его:

Часть выполненной работы