Графический метод решения задач ЛП

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

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

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

Линией уровня называется прямая, на которой целевая функция принимает постоянное значение. Уравнение линии уровня имеет вид

, где . Все линии уровня параллельны между собой. Их нормаль .

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

Значения возрастают в направлении вектора Поэтому необходимо передвигать линию уровня в направлении этого вектора параллельно самой себе до опорной прямой L1 в задаче на максимум и в противоположном направлении – в задаче на минимум (до опорной прямой L2).

20.Основная теорема ЛП говорит, что эктремум находится в вершинах многоугольника, но можно использовать градиентный метод. gradZ-это вектор, координаты которого являются частными производными(т.е. показывают максимальное изменение функций)

21.Транспортная задача (ТЗ): постановка задачи и ее математическая модель.

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

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

Систему ограничений получаем из следующих условий:

а) все грузы должны быть вывезены, т.е. (эти уравнения получаются из строк);

б) все потребности должны быть удовлетворены, т.е. .

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

– найти минимум линейной функции

при ограничениях

В рассматриваемой модели предполагается, что суммарные запасы равны суммарным запросам потребителей:

Такая задача называется задачей с правильным балансом, а её модель – закрытой. Если же равенство (7.1.4) не выполняется, то задача называется задачей с неправильным балансом, а её модель – открытой.