Графический метод решения задач линейного программирования

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К РЕШЕНИЮ ЗАДАЧ

Графический метод решения задач линейного программирования.

Общей задачей линейного программирования ОЗЛП называется задача, которая состоит в определении максимального (минимального) значения линейной целевой функции:

при условиях-ограничениях:

где - заданные постоянные величины и .

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

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 2 и 4, где и .

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

План , при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным.

В случае, когда требуется найти минимум функции , можно перейти к нахождению максимума функции , так как .

Ограничение-неравенство исходной задачи линейного программирования, имеющее вид “ ”, преобразуется в ограничение-равенство добавлением к левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида “ ” – в ограничение-равенство вычитанием из левой части дополнительной неотрицательной переменной.

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

План называется опорным планом основной задачи линейного программирования, если система векторов, входящих в разложение с положительными коэффициентами , линейно независима.

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

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

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

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

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

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

Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто). Непустое множество планов называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.

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

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

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

При условиях

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

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

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

1. на плоскости стоят прямые, уравнения которые получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств

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

3. строят многоугольник решений.

4. строят вектор , направление которого указывает на возрастание целевой функции.

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

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

Минимальное значение линейной функции цели находиться путем передвижения начальной прямой , в направлении, противоположному вектору

Пример.

Найти максимум и минимум линейной функции:

при условиях:

Решение:

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

Date: 2016-05-15; view: 670; Нарушение авторских прав