2. Линейное программирование

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

Пусть станция технического обслуживания автомобилей выполняет два вида обслуживания: ТО-1 и ТО-2.

Автомобили принимаются в начале рабочего дня и выдаются клиентам в конце дня.

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

Рабочий день длится 8 часов.

Если бы все автомобили прохо­дили только ТО-1, то мощности станции позволили бы обслу­жить 200 автомобилей в день, если бы все автомобили прохо­дили только ТО-2, то 50 автомобилей в день.

Стоимость (для клиента) ТО-2 вдвое выше, чем ТО-1, Реально за день часть автомобилей проходит ТО-1, а часть — ТО-2.

Требуется со­ставить такой дневной план обслуживания, чтобы обеспе­чить предприятию наибольшие денежные поступления.

Построим математическую модель задачи. Плано­выми показателями являются:

х — дневной план выполнения ТО-1;

у — дневной план выполнения ТО-2.

Что в этом примере можно назвать ресурсами производства? Из условия задачи ресурсами являются:

длительность рабочего дня — 8 часов;

вместимость стоянки — 140 мест.

Предполагается для простоты, что другие ресурсы не ограничены. Получим математические соотношения, следу­ющие из условий ограниченности ресурсов.

Из постановки задачи следует, что на ТО-2 затрачивается в 4 раза больше времени, чем на ТО-1. Если обозначить про­должительность ТО-1 как t мин., то продолжительность ТО-2 составит 4t мин. Стало быть, суммарное время на выполне­ние х обслуживаний ТО-1 и у обслуживаний ТО-2 равно:

tx +4ty = (x + 4y)t.

Но это время не может быть больше длительности рабоче­го дня. Отсюда следует неравенство:

(x+4y)t <= 8*60 (мин)

или

(x+4y)t <= 480.

Легко посчитать t — время для выполнения ТО-1. Посколь­ку за рабочий день обслуживаний вида ТО-1 может быть вы- полнено 200, то на одно ТО-1 тратится 480/200 = 2,4 (мин). Подставляя это значение в неравенство, получим:

(х + 4у) * 2,4 < = 480.

Отсюда:

х + 4у <= 200,

Полученное выше значение 2,4 мин. есть не физическое время выполне­ния одного ТО-1, поскольку оно требует много большего вре­мени, а среднее время для данной станции, имеющей, при такой большой производительности, несколько боксов.

Ограничение на вместимость стоянки дает совершенно очевидное неравенство:

х + у < =140.

К двум полученным неравенствам следует добавить усло­вия положительности значений величин х и у (не может быть отрицательного числа автомобилей). В итоге мы полу­чили систему неравенств:

(1)

Перейдем к формализации стратегической цели: получить максимальные денежные поступления. Пусть стоимость выполнения одного ТО-1 составляет r руб. По усло­вию задачи стоимость выполнения одного ТО-2 в два раза больше, т.е. 2r руб. Отсюда полная выручка предприятия за день равна

rх + 2rу =r(х + 2у).

Поскольку r — константа, то максимальное значение полной выручки будет достигнуто при максимальном значе­нии функции

f(x,y) = x + 2y (2)

В задачах оптимизации функцию, экстремум которой необходимо найти, называют целевой функцией, а систему неравенств (или уравнений) типа (1) системой огра­ничений.

Следовательно, получение оптимального плана свелось к следующей математической задаче: найти значения плано­вых показателей х и у, удовлетворяющих системе ограничений (1) и придающих максимальное значение целевой функции (2).

Построение математической модели задачи оп­тимального планирования для цеха станции технического обслуживания автомобилей завершено.

Математическая дисциплина, которая посвящена реше­нию задач подобных той, что рассмотрена выше, называется ма­тематическим программированием.

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

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

Каждое из неравенств, входящих в (1), задает на коор­динатной плоскости ху некоторую полуплоскость.

Система неравенств представляется пересечением четырех полуплос­костей.

На рис. 1 эта область представляет собой четы­рехугольник ABCD (область М), образованный четырьмя прямыми, соответствующими линейным уравнениям:

Любая точка четырех­угольника является решением системы неравенств (1). Пунктирные линии — семейство прямых, удовлетворяющих уравнению

f(x, у) = х + 2у = с (с — произвольная константа, значение целевой функции).

Вполне очевидно, что наиболь­шему возможному значению f совместному с условиями (1), соответствует жирная пунктирная линия, соприкаса­ющаяся с областью М в точке В.

Этой линии соответствует значение f = 160. Пунктирные линии, расположенные выше,

Рис.1. Графическое решение задачи об оптимальном плане работы станции технического обслуживания автомобилей

хотя и соответствуют большим значениям f, но не имеют общих точек с М, линии ниже соответствуют меньшим значе­ниям f.

Координаты точки В: х = 120, у = 20 — искомый оп­тимальный план.

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

Представьте себе, что тако­вых хотя бы три (например, в той же задаче рассмотреть и выполнение ТО-3) — тогда нам уже не удастся отображать зависимости между величинами линиями на плоскости.