Задача линейного программирования

Впервые постановка задачи линейного программирования в виде предложения по составлению оптимального плана перевозок, позволяющего минимизировать суммарной километраж, была дана в работе советского экономиста А. Н. Толстого в 1930 году.

Систематические исследования задач линейного программирования и разработка общих методов их решения получили дальнейшее развитие в работах российских математиков Л. В. Канторовича, В. С. Немчинова и других математиков и экономистов. Также методам линейного программирования посвящено много работ зарубежных и прежде всего американских ученых. Задача линейного программирования состоит в следующем: максимизировать (минимизировать) линейную функцию:

При ограничениях:

Причем все:

Замечание. Неравенства могут быть и противоположного смысла. Умножением соответствующих неравенств на (-1) можно всегда получить систему вида (*). Если число переменных системы ограничений и целевой функции в математической модели задачи равно 2, то её можно решить графически. Итак, надо максимизировать функцию:

И удовлетворяющей системе ограничений.

Обратимся к одному из неравенств системы ограничений:

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

Замечание 2. Если b1 не равно 0, то проще взять точку (0,0).

Условия не отрицательности также определяют полуплоскости соответственно с граничными прямыми. Будем считать, что система неравенств совместна, тогда полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты которых являются решением данной системы — это множество допустимых решений. Совокупность этих точек (решений) называется многоугольником решений. Он может быть точкой, лучом, многоугольником, неограниченной многоугольной областью. Таким образом, задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция принимает максимальное (минимальное) значение.

Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху (снизу). При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим прямую (где h — некоторая постоянная). Чаще всего берется прямая. Остается выяснить направление движения данной прямой. Это направление определяется градиентом (антиградиентом) целевой функции:

Вектор в каждой точке перпендикулярной прямой:

Поэтому значение f будет возрастать при перемещении прямой в направлении градиента (убывать в направлении антиградиента). Для этого параллельно прямой проводим прямые, смещаясь в направлении градиента (антиградиента).

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

Итак, нахождение решения задачи линейного программирования геометрическим методом включает следующие этапы:

• 1. Строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств;
• 2. Находят полуплоскости, определяемые каждым из ограничений задачи;
• 3. Находят многоугольник решений;
• 4. Строят вектор:
• 5. Строят прямую:

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

7. Определяют координаты точки максимума (минимума) функции и вычисляют значение целевой функции в этой точке.

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

Для их погрузки выделяются три станции, с различными возможностями. Перевозка соединений осуществляется с соблюдением следующих ограничений:

• 1. Количество перевозимых частей в соединении А1 равно 6, а в -9;
• 2. Каждая станция может принять определенное количество частей;
• 3. На погрузку одной части станции затрачивают различное время (в сутках), которое указано в таблице.

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

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

Обозначим через число частей i-го соединения (i =1,2) на j-ой станции (j=1, 2, 3).

Мы можем записать:

Количество частей соединений на станциях погрузки соответственно:

Общая сумма затрат времени (в сутках) на погрузку есть:

В этой задаче 6 переменных, но мы можем свести к двум:

Итак, при ограничениях:

Которая решается графически.

Возьмем прямую:

И начнем строить параллельные ей в направлении антиградиента:

Последняя вершина многоугольника решений есть точка С, получаемая пересечением прямых (1) и (4). Решая, получим С (1;5).

Итак, оптимальные значения будут следующими: