11. Методы решения злп. Графический и симплекс метод. Соответствие базисных решений. Положительные и отрицательные моменты.

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

Этап 1. На координатной плоскости Х₁0X₂ строится область допустимых решений, соответствующая ограничениям. Далее строится вектор-градиент линейной функции F(X) в какой-нибудь точке х₀ , принадлежащей допустимой области:

Этап 2. Прямая c₁x₁+ c₂x₂= f(x₀), перпендикулярная вектору-градиенту, передвигается в направлении этого вектора в случае максимизации f(X) до тех пор, пока не покинет пределов многоугольной области. Предельная точка (или точки) области при этом движении и является точкой максимума F(X).

Этап 3. Для нахождения координат точки максимума достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение F(X), найденное в получаемой точке, является максимальным.

В случае минимизации F(X) прямую c₁x₁+ c₂x₂= f(x₀) надо двигать в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает допустимой области, то соответствующий мак или мин f(X) не существует.

Выводы:

+ прост, нагляден, позволяет быстро и легко получить ответ.

- "Технические" погрешности, кот. неизбежно возникают при приближенном построении графиков. Многие величины, имеющие четкий экономический смысл (такие, как остатки ресурсов произ-ва, избыток питательных веществ и т.п.), не выявляются при геометрич. решении задач. Не приемлем для решения практических задач, когда n>2.

Симплексный метод: Практическое осуществление перебора всех угловых точек многогранника решений связано с огромными трудностями. Число перебираемых допустимых базисных решений можно сократить, если производить перебор с учетом изменений линейной функции. Такой перебор позволяет сократить число шагов при отыскании оптимума. Этот метод последовательного улучшения решения называется симплексным. Если ЗЛП имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает с одним из допустимых базисных решений системы ограничений.

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

Для реализации этого метода необходимо освоить три основных элемента:

1. Способ определения какого-либо первоначального допустимого базисного решения задачи.

2. Правило перехода к лучшему решению.

3. Критерий проверки оптимальности найденного решения.

12. Двойственные злп. Экономическая интерпретация на примере задачи планирования производства. Правило построения дз.

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

Пусть имеются две задачи линейного программирования обладающие следующими особенностями:

1. В одной задаче ищут максимум линейной функции, в другой — минимум;

2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой;

3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида "", а в задаче минимизации — все неравенства вида "";

4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу:

Для задачи I: _. Для задачи II: _.

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче;

6. Условия неотрицательности переменных имеются в обеих задачах,

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

Экономическое значение двойственности.

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

b_i - запас ресурса S_i;

a_ij — число единиц ресурса S_i, потребляемого при производстве единицы продукции Pj;

с_j - цена продукции Pj.

Допустим, что некоторая сторонняя организация решила закупить ресурсы S₁, S₂,...,S_m. Необходимо установить оптимальные цены на эти ресурсы y₁, y₂, ..., у_т.

Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах b₁, b₂, ..., b_т по ценам соответственно y₁, y₂, ..., у_т были минимальны, т.е

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

a₁₁ единиц ресурса S₁,

a₂₁ единиц ресурса S₂,

...

a_m1 единиц ресурса S_m,

по цене соответственно у₁, y₂, ..., y_i, ..., у_n. Поэтому для удовлетворения требований продавца предлагаемая цена за ресурсы, потребляемые при изготовлении единицы продукции Р₁, должны быть не менее цены продукта с1, т.е.

Аналогично можно составить ограничения в виде неравенств по каждому виду продукции.

Задача 1 (исходная) F= с₁х₁ + с₂х₂ +...+ с_nх_n →max

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

и условии

Составить такой план выпуска продукции

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

Задача 2 (двойственная) Z= b₁y₁ + b₂y₂ +...+ b_my_m →min

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

и условии

Найти такой набор цен (оценок) ресурсов

Y = (y₁, y₂, ..., у_n), при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции.

Цены ресурсов у₁, у₂, ..., у_т называются учетными, неявными, теневыми. Смысл этих названий состоит в том, что это условные, "ненастоящие" цены. В отличие от внешних цен с₁, с₂, ..., с_n на продукцию, известных, как правило, до начала производства, цены ресурсов у₁, y₂, ..., у_т являются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.

Правила построения двойственной задачи:

1. Если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду "", а если минимум — к виду "". Для этого неравенства, в которых данное требование не выполняется, умножить на -1.

2. Составить расширенную матрицу системы А₁, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

3. Найти матрицу , транспонированную к матрице А₁.

4. Сформулировать двойственную задачу на основании полученной матрицы и условия неотрицательности переменных.