Определение соотношения между количеством скорых и курьерских поездов

Задача №1

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

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

Решение:

Пусть х₁  - число курьерских поездов;

х₂ - число скорых поездов;

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

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

Выберем линию уровня F=0

626×x₁ + 656×x₂ = 0     

Функция F имеет оптимум в точках А, В или С. Определим точку минимума с помощью основной теоремы линейного программирования.

Строим F=0, затем строим градиент grad F.

Двигая линию уровня в направлении градиента определим точки области значений с которой соприкасается линия уровня – эта точка и определит координату оптимального решения.

Решением является точка А с координатами х₁=5, х₂=7.

F_max = 7722.

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

Дополним неравенство до равенства

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

Получаем решение: Число перевозимых пассажиров будет максимально (7722 чел.), если с железнодорожного вокзала ежедневно отправлять 5 курьерских и 7 скорых поездов. При этом невостребованными останутся 12 купейных, 5 мягких и 1 почтовый вагон.

Двойственная задача.

Математическая модель двойственной задачи подчиняется следующим правилам:

Ø  Количество двойственных переменных равно количеству ограничений в исходной задаче;

Ø  F_max ® Z_min и наоборот;