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

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

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

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

Областью решений линейного неравенства a_i1x₁ + a_i2x₂ ≤ b_i является одна из двух полуплоскостей, на которые прямая a_i1x₁ + a_i2x₂ = 0, соответствующая данному неравенству, делит всю координатную плоскость.

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

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

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

Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение линии уровня в общем случае имеет вид c₁x₁ + c₂x₂ = l, где l = const. Все линии уровня параллельны между собой. Их нормаль n = (c₁, c₂).

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

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

Алгоритм нахождения решения задачи

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

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

3. Находят многоугольник решений.

4. Строят вектор C = (c₁, c₂).

5. Строят прямую c₁x₁ + c₂x₂ = h, проходящую через многоугольник решений.

6. Передвигают прямую c₁x₁ + c₂x₂ = h в направлении вектора C, в результате чего либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов.

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

Задача об использовании ресурсов

Для изготовления двух видов продукции P₁ и P₂ используют четыре вида ресурсов S₁, S₂, S₃, S₄. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице (цифры условные).

Прибыль, получаемая от единицы продукции P₁ и P₂, ˗˗ соответственно 2 и 3 рубля.

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

Решение

Задача составления рациона

Имеется два вида корма I и II, содержащие питательные вещества (витамины) S₁, S₂ и S₃. Содержание числа единиц питательных веществ в 1кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице (цифры условные).

Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб.

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

Решение