1 Стандартная задача Матричная форма записи § 1.4. Специальные виды задач ЛП максимизации минимизации Обозначения

2 Каноническая задача Матричная форма записи максимизации минимизации

3 Эквивалентные преобразования Нахождение максимума линейной функции эквивалентно нахождению минимума этой функции, взятой с противоположным знаком, и наоборот: Если на переменную не накладывается условие неотрицательности, то ее можно заменить разностью двух неотрицательных переменных:

4 Если имеется n переменных без ограничения на знак, то их можно заменить n+1 неотрицательной переменной: Ограничение типа неравенства можно представить в виде равенства, используя слабые переменные, следующим образом:

5 Ограничение типа равенства можно заменить двумя неравенствами: Если имеется m равенств, то их можно заменить m+1 неравенством: Знак неравенства можно заменить на противоположный, умножив данное неравенство на (-1)!

6 Пример Представить задачу ЛП в стандартной и канонической формах максимизации: каноническая задача максимизации:

7 стандартная задача максимизации:

8 § 1.5. Базисное решение системы линейных уравнений Будем считать, что СЛУ AX = B совместна (имеет решение), следовательно выполнено условие: 1. Решение единственно: 2. Бескон. множество решений:

Базисным решением СЛУ, зависящим от множества индексов, будем называть решение СЛУ, которое находится по правилам: привести данную систему, используя метод Гаусса, к диагональной форме по переменным ( базисные переменные) переменные называются небазисными, возьмем получим 9 Базисное решение

10 Замечание Базисное решение не может содержать более чем m отличных от нуля элементов. Замечание Если базисное решение содержит ровно m отличных от нуля компонент, то оно называется невырожденным базисным решением. В противном случае – вырожденным базисным решением. Замечание Если все компоненты базисного решения неотрицательные, то такое базисное решение называется допустимым базисным решением. Замечание Количество базисных решений СЛУ не может превышать величину

11 Пример Найдем все базисные решения системы ЛУ: Максимальное количество базисных решений : доп. невырожд. баз. решение не доп. невырожд. баз. решение доп. невырожд. баз. решение

12 Утверждение Если у системы линейных уравнений существует решение, то существует и базисное решение этой системы ЛУ. Утверждение Если задача ЛП имеет допустимое решение, то она имеет и допустимое базисное решение. Утверждение Если задача ЛП имеет оптимальное решение, то она имеет и оптимальное базисное решение. § 1.6. Алгоритм симплекс-метода решения задачи ЛП

13 Пример (неформальное решение ЗЛП симплекс-методом) Рассмотрим задачу ЛП : z-уравнение Преобразуем целевую функцию к виду:

14 вводим в базис выводим из базиса 1-е базисное решение Выразим базисные переменные из системы

15 2-е базисное решение 15 вводим в базис выводим из базиса Выразим базисные переменные из системы

16 3-е базисное решение оптимальное решение

17 Перейдем к описанию формального алгоритма симплекс-метода для канонической задачи максимизации: Выполним ряд вспомогательных построений. По задаче ЛП запишем СЛУ, рассматривая целевую функцию как одно из ограничений (z-уравнение):

18 Приведем данную систему к диагональной форме по переменным z,

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

20 Классификация симплексных таблиц: симплексная таблица называется прямо-допустимой, если симплексная таблица называется свойств.-допусти- мой, если симплексная таблица называется оптимальной, если она одновременно прямо- и свойственно допустимая, соответствует оптимальному базисному решению.

Если все то текущее базисное решение является оптимальным. 21 Алгоритм прямого симплекс-метода (максимизация) 0. Проверка прямо-допустимости. В противном случае в базис вводим переменную номер которой находится по правилу: Столбец s называется ведущим столбцом СТ. 1. Проверка оптимальности или нахождение ведущего столбца СТ. ИТЕРАЦИЯ

22 2. Проверка неограниченности или нахождение ведущей строки СТ. Если в ведущем столбце все коэффициенты В противном случае следует выводить из базиса переменную, для которой: Строка с номером r называется ведущей строкой СТ, 3. Преобразование СТ. то решение задачи неограниченно. ведущим элементом СТ.

23 Ведущий столбец Ведущая строка

24 Пример Решим задачу из примера с помощью СТ: Приведем к каноническому виду и составим диагональную форму для СЛУ zx1x1 x2x2 s1s1 s2s2 z s1s s2s

25 zx1x1 x2x2 s1s1 s2s2 z10001 s1s1 203/51-1/5 x1x1 212/501/5 Итерация 3. zx1x1 x2x2 s1s1 s2s2 z40/3005/32/3 x2x2 10/3015/3-1/3 x1x1 2/310-2/31/3 zx1x1 x2x2 s1s1 s2s2 z s1s s2s Итерация 2. Итерация 1. Оптимальное решение

26 Геометрическая интерпретация расчетов по симплекс-методу: 1-ое базисное решение 2-ое базисное решение 3-ье базисное решение

Прямая задача Двойственная задача § 1.7. Прямая и свойственная задачи ЛП.

28 Пример Запишем свойственную задачу к задаче:

29 Частные случаи Прямая задача Двойственная задача

30 Экономическая интерпретация пары стандартных свойственных задач ЛП: Оптимальный план производства максимизирующий суммарную прибыль при ограничении на запасы ресурсов. – прибыль, приходящаяся на единицу продукции, – запас ресурса, – расход ресурса на единицу продукции, Оптимальные цены ресурсов минимизирующие суммарные затраты при ограничении на стоимость продукции.

умножим на Y слева: 31 Теоремы свойственности и равновесия в линейном программировании умножим на X справа: Лемма (Свойство допустимых решений) Пусть X и Y – произвольные допустимые решения задач (1.7.1) и (1.7.2). Тогда Док-во: тогда Стандартная пара свойственных задач

возьмем X* : X и Y – произвольные допустимые решения, тогда для любого X, выполнено Лемма (Достаточное условие оптимальности) Доказательство: Пусть X* и Y* – произвольные допустимые решения задач (1.7.1) и (1.7.2), для которых выполнено равенство Тогда X* и Y* – оптимальные решения задач ЛП. следовательно, Y * – оптимальное решение.

33 Если хотя бы одна из задач ЛП (прямая или свойств.) не имеет допустимого решения, то обе задачи ЛП не имеют оптимальных решений. Теорема (Двойственности). Если обе задачи ЛП (и прямая, и свойственная) имеют допустимые решения, то обе задачи имеют оптимальные решения X* и Y*, причем Замечание Теорема свойственности справедлива для любой пары свойственных задач.

34 Иллюстрация теоремы

35 Теорема (Критерий оптимальности) Для того чтобы пара допустимых решений X* и Y* задач (1.7.1) и (1.7.2) была парой оптимальных решений соответствующих задач, необходимо и достаточно, чтобы Теорема (Стандартная теорема равновесия) Для того чтобы пара допустимых решений X* и Y* задач (1.7.1) и (1.7.2) была парой оптимальных решений соответствующих задач, необходимо и достаточно, чтобы

36 и Следствие. (Критерий оптимальности для стандартной задачи ЛП). Для того чтобы пара допустимых решений задач (1.7.1) и (1.7.2) была парой оптимальных решений, необх. и дост., чтобы выполнялись соотношения:

37 Пример Прямая задача Оптимальное решение Двойственная задача Критерий оптимальности Оптимальное решение

38 Пример Оптимальное решение Прямая задача Двойственная задача Оптимальное решение Критерий оптимальности

39 Теорема (Канон. теорема равновесия) Для того чтобы пара допустимых решений X* и Y* задач (1.7.3) и (1.7.4) была парой оптимальных решений соответствующих задач, необх. и дост., чтобы Следствие. (Критерий оптимальности) Для того чтобы пара допустимых решений X* и Y* задач (1.7.3) и (1.7.4) была парой оптимальных решений соответствующих задач, необх. и дост., чтобы (1.7.4) (1.7.3) Каноническая пара свойственных задач