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

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

На рис.2 опорная прямая совпадает с одной из сторон многоугольника решений. Оптимальным решением является любая выпуклая линейная комбинация точек отрезка АЕ.

На рис.3 ОДР не ограничена в сторону увеличения значений Z(X).

Пример 1. Решим графически задачу ЛП:

Построим многоугольник решений (рис.4). Для этого в системе координат X10X2 на плоскости изобразим граничные прямые:

3х1 + 2х2 = 13 (L2);

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

Строим линию уровня Z = 3х1 + 4х2 = 0 и вектор-градиент . Прямую Z = 0 перемещаем параллельно самой себе в направлении вектора . Из рис.4 следует, что по отношению к многоугольнику решений опорной эта прямая становится в точке C, где функция принимает максимальное значение.

Точка С лежит на пересечении прямых L1 и L3. Для определения ее координат решим систему уравнений:

Оптимальный план задачи х1=2,4; х2=1,4. Подставляя значения х1 и х2 в линейную функцию, получим:

.

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

Приведение задач ЛП к канонической форме

Если математическая модель задачи ЛП имеет вид:

(1)

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

Более компактная запись:

(2)

(1) и (2) – координатные записи канонической задачи ЛП.

Векторная запись канонической задачи:

где (3)

Матричная запись канонической задачи:

(4)

где

Любую задачу ЛП можно свести к канонической по следующим правилам.

1. Переход от задачи на max к задаче на min (и обратно) осуществляется изменением знака целевой функции

.

Исходная и полученная задачи имеют одно и то же оптимальное решение Х*, а значения целевых функций на этом решении отличаются лишь знаком.

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

→

→ .

В целевую функцию дополнительные переменные вводятся с нулевыми коэффициентами, в этом случае они не влияют на значение Z(X)

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

Пример 1. Приведем к канонической форме (на минимум) задачу ЛП:

1. Перейдем к задаче на минимум

2. Введем в каждое ограничение системы ограничений выравнивающие переменные x4, x5, x6. Система запишется в виде равенств.

.

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

Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу ЛП, представленную в канонической форме:

Принцип работы симплекс-метода

Решение задач ЛП на основе симплекс-метода состоит в целенаправленном переборе угловых точек ОДР в направлении улучшения значения целевой функции.

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

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

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

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

1.Задача приводится к канонической форме.

2.Строится исходная симплекс-таблица и определяется начальное допустимое решение (начальная угловая точка).

3.Выполняются преобразования симплекс-таблиц, соответствующие перебору угловых точек ОДР, до получения оптимального решения.

Рассмотрим реализацию данного алгоритма при решении задачи линейного программирования:

где .

1. Перепишем задачу в каноническом виде, добавив дополнительные неизвестные :

где

2. Запишем первую симплекс-таблицу:

Если в последней строке (среди чисел —c1,…., —c2) нет отрицательных коэффициентов, то базисное решение (когда свободные неизвестные х1 =…= хn =0) будет оптимальным. Действительно, если увеличить от 0 хотя бы одно из свободных неизвестных, то функция будет убывать.

Пусть, например, —c1 0, то при равенстве 0 всех остальных свободных неизвестных х1 можно увеличивать не более чем до числа b1/a11. Если a110, то неравенство не накладывает ограничений на рост числа х1 (тогда х1 можно увеличивать сколько угодно). Поэтому, если все коэффициенты a11,…, ak1 неположительны, то х1 может расти неограниченно и, при этом, функция будет нарастать также неограниченно. В этом случае оптимального решения нет.

3. Ограничимся случаями, когда в первом столбце среди чисел a11,…, ak1 есть положительные коэффициенты:, тогда число х1 можно увеличивать до величины x0=min. Пусть min достигается в строке и пусть i1=1. Перейдем к базису, переводя х1 в базис вместо хn+1. Получим новую симплекс-таблицу, для которой значение функции возрастет на число с1 х0>0.

Для новой симплекс-таблицы, если в последней строке нет отрицательных коэффициентов, соответствующее базисное решение будет оптимальным (функция имеет вид , где числа ,…, 0 и поэтому увеличивать числа х1,…, хn+1 невыгодно). Если в последней строке будет отрицательный коэффициент, то выполняем предыдущую процедуру (по переходу к новой симплекс таблице) еще раз. За конечное число шагов мы получим оптимальное базисное решение или докажем, что оптимального решения нет.

Пример 2. Для выполнения работ по изготовлению изделий 1-го и 2-го типа имеется 10 единиц 1-го сырья и 8 единиц 2-го сырья. На каждое изделие 1-го типа расходуется по 2 единицы каждого сырья, а для каждого изделия 2-го типа расходуется 4 и 1 единицы сырья каждого типа. Спланировать производство так, чтобы суммарное число изделий было наибольшим.

Пусть изделий 1-го и 2-го типа производится x1 и x2 единиц, тогда сырья 1-го типа будет израсходовано , а сырья 2-го типа . Требуется найти максимум функции при неотрицательных целых значениях аргумента.

Введем вспомогательные неизвестные x3 и x4 (остатки сырья 1-го и 2-го типа) и получим каноническую задачу:

где

Видео:Графический метод решения задачи линейного программирования (ЗЛП)Скачать

Целевая функция в задаче ЛП с двумя переменными

В задаче с двумя переменными целевая функция имеет вид

Предположим, что Z = 3x₁ + x₂. Выясним, как графически можно представить целевую функцию в координатной плоскости Х₁0Х₂. Для этого придадим Z какое-либо постоянное значение, например, Z= 3. Тогда получаем

Это уравнение задает в координатной плоскости Х₁0Х₂ прямую с угловым коэффициентом, равным (-3). Напомним, что угловой коэффициент прямой — это коэффициент, стоящий при аргументе х₁, который равен тангенсу угла наклона прямой к оси 0Х₁ и, следовательно, задает ее наклон. Нанесем эту прямую на график, представленный на рис. 3.5. Заметим, что для всех точек, принадлежащих данной прямой, значение целевой функции одинаково (постоянно) и равно 3, поскольку все точки прямой удовлетворяют уравнению 3х₁ + x₂=3.

Положим теперь Z = 5. Тогда в Х₁0Х₂ получаем новую прямую (рис, 3.5), уравнение которой

Заметим, что угловой коэффициент новой прямой, также как и первой (Z = 3), равен (-3). Следовательно, прямые Z=3и Z=5 параллельны друг другу.

Пусть теперь Z = 6. Рассуждая аналогично, можно построить на графике прямую, задаваемую и этим уравнением. Она также будет параллельна первым двум прямым линиям Z = 3 и Z = 5, поскольку угловой коэффициент и в этом случае остался равным (-3).

Причем по мере удаления от начала координат величина Z возрастает, а при перемещении к началу координат — уменьшается. Легко прийти к выводу: разным значениям целевой функции Z соответствует семейство параллельных прямых.

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

• Если задана функция двух переменных Z = f(x₁ х₂), то линии в Х₁0Х₂ для которых Z = f(x₁ х₂) = const, называют линиями уровня. Иначе говоря, это те линии, во всех точках которых величина Z постоянна.

• В задачах линейного программирования линиями уровня являются прямые Z = const. Во всех точках, принадлежащих какой-либо линии уровня, значение целевой функции одинаково.

• Важным свойством линий уровня для линейных целевых функций является то, что при их параллельном смещении в одну сторону величина Z только возрастает, а при перемещении в другую сторону — только убывает.

• Определить направление возрастания целевой функции можно с помощью специального вектора, называемого градиентом функции Z = f(x₁ х₂). Для его обозначения используют символ .

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

• В задачах линейного программирования с целевой функцией Z = с₁х₁ + c₂x₂ координатами вектора являются его коэффициенты: = (с₁, c₂) (рис. 3.6).

=(с1,с2)

x₂

Эти утверждения позволяют строить только одну прямую Z = const и далее определять с помощью вектора с координатами = (c₁,c₂), в каком направлении целевая функция Z будет возрастать, а в каком убывать.

Проведенный анализ позволяет сделать следующие выводы.

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

• Линии уровня в задачах линейного программирования с двумя переменными — это прямые, во всех точках которых величина Z постоянна.

• Вектор = (с₁ ,c₂), где с₁, с₂ — коэффициенты целевой функции, позволяет определить, в какую область значений параметров оптимизации x₁ и х₂ следует перемещаться, чтобы величина Z возрастала (при ее максимизации) либо убывала (при ее минимизации).

• При изменении коэффициентов (c₁, c₂) целевой функции Z = с₁х₁+ c₂x₂ линии уровня меняют наклон и направление возрастания.

💡 Видео

Линейное программирование Часть 1. Постановка задачиСкачать

Решение задачи линейного программирования при помощи надстройки Поиск решенияСкачать

СИМПЛЕКС МЕТОД: ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯСкачать

Линейная функция: краткие ответы на важные вопросы | Математика | TutorOnlineСкачать

Cимплексный метод решения задачи линейного программирования (ЗЛП)Скачать

Математика без Ху!ни. Функции нескольких переменных. Область определения. Линии уровня.Скачать

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

Лекция 1. Комментарии к дистанционной лекции по линейному программированию.Скачать

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

Урок 2. Экономический смысл двойственной задачиСкачать

Линейное программированиеСкачать

Практическая работа "Решение задач линейного программирования графическим методом".Скачать

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

Лекция 4 Анализ чувствительности решения задачи линейного программированияСкачать

Симплексный метод (табличный оформление №1) решения задачи линейного программирования.Скачать

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

Поверхности и линии уровняСкачать