Методы оптимизации Курс лекций



МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

«Нижегородский государственный университет им. Н.И. Лобачевского»

Экономический факультет

Кафедра экономической информатики

                                     В.С. Громницкий

Методы оптимизации

Курс лекций

Рекомендован методической комиссией экономического факультета для студентов высших учебных заведений, обучающихся по специальности 080801 «Прикладная информатика (в экономике)»

Нижний Новгород

2010

УДК 65.012.122 (075.8)

ББК Ув6я73

Г 87

Г87 Громницкий В.С.Методы оптимизации. Курс лекций: Учебное пособие – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2010. – 104 с.

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

Приводится классификация задач принятия решений, дается понятие математического моделирования. Подробно  излагаются методы линейного программирования, включая теорию двойственности и послеоптимизационный анализ. Даются основы нелинейного программирования.

Пособие предназначено для студентов экономического факультета университета, обучающихся по специальности «Прикладная информатика в экономике», может быть полезно для  научных и практических работников, занимающихся вопросами моделирования и оптимизации экономических процессов.

Рецензент: доцент, к.э.н. Пчелинцев Александр Дмитриевич

ББК Ув6я73

© Громницкий В.С., 2010

                © Нижегородский государственный

                          университет им. Н.И. Лобачевского, 2010

Содержание

Введение

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

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

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

Система(A,B,C) и выходные (). Задача анализа системы ставится как задача принятия решений, то есть задача выбора таких управляемых параметров, которые обеспечивают наилучшие показатели деятельности системы. Цели функционирования системы могут быть разные и обычно формулируются постановщиком задачи, лицом принимающим решения.

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

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

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

Задачи принятия решений

Исследование операций включает в себя целый ряд научных дисциплин, отличающихся целями и методами принимаемых решений:

где

Задача (1–2) относится к классу экстремальных задач. Если область допустимых решенийD совпадает с пространством вещественных чиселR, то есть отсутствуют ограничения (2),то данная экстремальная задача является классической задачей оптимизации.

Математическое моделирование

Моделирование – замена одного объекта другим с целью изучения их общих свойств.

По средствам моделирования методы моделирования можно разбить на две группы: методы материального моделирования и методы идеального моделирования.

Материальным моделирование называется в том случае, когда копия объекта – модель имеет материальный характер.

В материальном моделировании можно выделить три группы методов: пространственное, физическое и аналоговое

Пространственное  моделирование изучает геометрические свойства объекта (макеты, карты, глобус).

Физическое моделирование  служит для воспроизведения и изучения динамических свойств объектов (летательных аппаратов, технических сооружений).

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

Идеальное моделирование основывается не на материальной аналогии модели и изучаемого объекта, а на идеальной, мыслимой связи между ними. Материальной копии не создается.

Методы идеального моделирования можно разбить на две группы: формализованное (знаковое) и неформализованное (интуитивное) моделирование.

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

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

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

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

ЧастьI. Линейное программирование

Глава 1. Линейные математические модели в экономических исследованиях

1.1. Экономические задачи

  1. Задача объемного планирования
    1. Содержательное описание

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

  1. Математическая модель

2.1.Исходные параметры

– количество видов продукции

– количество типов ресурсов

– запасы ресурсов каждого вида

– нормы расходаi-го ресурса на единицуj-ой продукции

– доход от единицыj-ой продукции

2.2.Управляемые параметры (варьируемые параметры)

– объемы производства каждого вида продукции

– вектор управляемых параметров (решение, допустимое решение – план)

2.3.Ограничения модели

Чаще всего ограничения в экономических задачах отражают соотношения материального баланса (расход ресурса не может превосходить его запасов).

Пусть –  расходi-го ресурса на произвольном плане .

  1. Формулировка цели принятия решений

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

Таким образом, задача объемного планирования ставится как задача определения такого набора управляемых параметров

,

на котором достигается наибольшее значение критерия

при условии

  1. Задача о диете
    1. Содержательное описание

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

  1. Математическая модель

2.1.Исходные параметры

– количество видов продукта

– количество контролируемых питательных веществ

– нормы потребления каждого питательного вещества (нижние границы)

– содержаниеi-го питательного вещества в единицеj-го продукта

– цена каждого продукта

2.2.Управляемые параметры (варьируемые параметры)

– объем закупок каждого продукта

– вектор управляемых параметров (решение, план закупок или рацион)

2.3.Ограничения модели

Пусть– содержаниеi-го питательного вещества в произвольном рационе .

Нужно выбрать наилучшее решение.

  1. Формулировка цели принятия решений

Сформулируем критерий оптимальности. Пусть – стоимость произвольного рациона . Требуется найти рацион наименьшей стоимости

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

,

на котором достигается наименьшее значение критерия

при условии

1.2. Общий вид математической модели задачи линейного программирования

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

Найти набор управляемых параметров

,

на  котором достигается наибольшее (наименьшее) значение показателя эффективности

при выполнении ограничений

и на некоторые переменные накладываются условия неотрицательности

Функция (7) называется целевой функцией или критерием оптимальности, или линейной формой.

Вектор управляемых параметровназывается решением. Решение называется допустимым, если оно удовлетворяет ограничениям (8–11). Допустимое решение называется планом.

Решение  называется оптимальным, если на нем достигается наибольшее значение критерия оптимальности:

– оптимальное решение, если

– оптимальное решение, если для любого

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

1.3. Различные формы задач линейного программирования

В зависимости от вида ограничений различают следующие формы задач:

Задача в канонической форме – задача ЛП, в которой все ограничения (8) – (10) есть равенства (p =q = 0) и все переменные неотрицательные (r =n).

Общий метод решения задачи ЛП разработан именно для задачи в каноническом виде.

Матричный вид задачи в канонической форме:

() = (*) →

=

=   – вектор коэффициентов критерия

=

=– матрица условий (технологических коэффициентов)

= ( )

=   – вектор условий

=    – вектор ограничений

() = (*)

+  + …+ =

,

Для неё разработан метод решения, который называется симплексным.

Задача в симметричной форме – задача ЛП, в которой все ограничения (8) - (10) есть неравенства (p =q =m) и все переменные неотрицательные (r =n).

Матричный вид задачи в симметричной форме:

Симметричная форма допускает графическое решение (иллюстрацию).

Задача в общей (смешанной) форме – задача ЛП, в которой присутствуют все виды ограничений и не все переменные неотрицательные.

эквивалентной формы к другой.

  1. Сведение задачи минимизации к задаче максимизации:

Преобразование сводится к смене знака критерия.

() ~ (())

() = (())

  1. Переход от ограничений-неравенств к уравнению:

+ =

Переменные  - дополнительные или балансовые, так как обеспечивают баланс правой и левой частей.

- =

  1. Переход от переменных произвольного знака к неотрицательным переменным:

=  -

  1. Переход от переменных, ограниченных снизу, к неотрицательным:

= +

  1. Переход от уравнений к неравенствам:
    • Если имеется уравнение:

то оно заменяется на два неравенства:

А также:

Пусть ранг (количество линейно-независимых уравнений) системы ограничений равен , тогда  переменных можно выразить через остальные:

Под решением систем уравнений(29) понимается зависимость одних переменных через другие. Эта зависимость(31) называется общим решением, независимые переменные – свободными (их можно произвольно менять), а – базисными переменными.

Задавая произвольные значения свободным переменным, получаем частные решения, но не все они удовлетворяют условиям неотрицательности:

Тогда для свободных переменных получаем ограничения в виде неравенств:

Если () = 2, то задача допускает иллюстрацию в пространстве двух переменных.

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

Примеры решения задач

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

  1. Записать задачу в симметричной форме.

1.4. Графическое решение задач

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

Пусть = 2, тогда задача ЛП в симметричной форме выглядит так:

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

Построим прямую .

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

Пересечение плоскостей образует область допустимых решений .

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

                                              (38)

Для задачи линейного программирования это прямые с разными константами в правой части уравнения (38).

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

Градиент – это вектор частных производных функции.

= = ()

Его можно вычислить в любой конкретной точке пространства переменных.

Свойства градиента функции

Пример

=

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

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

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

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

Пример

Решим графически задачу 2 из примеров раздела 1.3.

– оптимальное решение двумерной задачи, в пространствеx2,x4.

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

– полное оптимальное решение пятимерной задачи.

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

Свойства области допустимых решений

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

2.1. Свойства области допустимых решений

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

Пусть все уравнения линейно-независимые.

ø

И пусть есть несколько - мерных векторов .

Выпуклая оболочка - мерных векторов – множество точек вида:

, ,

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

,

Двумерное пространство

Трехмерное пространство

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

Теорема 1: Область допустимых решений  задачи ЛП выпуклая.

Доказательство:

Пусть , т.е. для них выполняются(2) и(3).

таким образом, условие(3)выполняется.

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

Теорема доказана.

Точка  называетсяугловой (крайней), если не существует двух других точек области, на отрезке между которыми лежит эта точка.

не , , , ,таких, что ,

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

Таким образом, если найти все угловые точки, то любая точка внутри области записывается через уравнение(4).

Теорема 2: Оптимальное решение задачи ЛП достигается в одной из угловых точек области допустимых решений .

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

Пусть   – внутренняя точка области. Тогда функция дифференцируема в этой точке:

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

Но это противоречит  условию, которое мы накладывали ранее, а именно . Значит точка, в которой достигается оптимальное решение, лежит на границе области. Можно показать [8], что хотя бы одно оптимальное решение достигается в угловой точке.

2.2. Базисные и опорные решения

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

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

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

Пример:

8

10

5

12

10

18

7

15

19

22

9

23

Проверим, опорное это решение или нет:

– опорное решение (невырожденное).

В трехмерном пространстве максимум только 3 вектора могут быть независимыми.

– не является опорным решением, так как векторы  линейно-зависимые. Значит, эта точка будет внутренней точкой области.

– опорное решение (вырожденное).

Так как определитель равен нулю, вектора линейно-зависимые.

– не является опорным решением.

Положительные компоненты опорного решения называютсябазисными.

Вектора условий линейных компонентов могут быть базисом в пространстве.

Базис - мерного пространства – совокупность любых  линейно-независимых векторов .

Опорное решение называетсяневырожденным, если количество положительных компонент равно числу линейно-независимых ограничений (k=m).

Опорное решение называетсявырожденным, если количество положительных компонент меньше числа линейно-независимых ограничений (k<m).

Нулевые переменные невырожденного опорного решения называютсясвободными.

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

Базисное решение – решение системы уравнений (2) , если вектора условий при егоненулевых компонентах линейно-независимые.

Базисная матрица – матрица из  линейно-независимых векторов условий, содержащая все вектора условий при ненулевых компонентах. Она всегда квадратная.

Базисная матрица невырожденного решения определяется однозначно, а базисная матрица вырожденного – неоднозначно.

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

Максимальное количество базисных решений равно .

Опорное решение – допустимое базисное решение. Для поиска опорных решений можно перебрать все базисные решения и выбрать из них допустимые (с неотрицательными компонентами).

Теорема 3: опорные решения задачи ЛП совпадают с угловыми точками области допустимых решений.

Доказательство теоремы смотри в[8].

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

3.1. Идея симплекс-метода

Симплекс в - мерном пространстве – простейший многогранник.

гранник

–треугольник

– тетраедр

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

Этапы симплекс-метода:

  1. Построение начального опорного плана .
  2. Проверяется признак оптимальности решения.
  3. Построение нового опорного решения – переход от одной вершины симплекса  к другой  .
  4. l=l+1, повторять со второго пункта до тех пор, пока не выполнятся условия оптимальности.

3.2. Векторное представление симплексных преобразований

Пусть имеется опорный план  и он невырожденный.

- базисная матрица.

- небазисная матрица.

Рассмотрим произвольное допустимое решение (это не угловая точка):

, подставим в условие (2).

Выразим базисные переменные через свободные и найдем общее решение системы уравнений:

Рассмотрим критерий на произвольном решении :

,

где

На опорном плане  свободные переменные равны нулю, поэтому

,

а критерий в произвольной точке области выразится через свободные переменные в виде

Теорема 4: Опорный план  задачи ЛП является оптимальным, если все оценки свободных переменных неотрицательны, т.е. .

Доказательство:

Для

т.к. , то и .

Значит решение  оптимальное, так как во всех точках области значение критерия меньше (), чем критерий в точке .

Теорема доказана.

3.3. Симплекс-метод в уравнениях

Рассмотрим симплексные преобразования на конкретном примере

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

Определить объемы производства двух видов продукции, обеспечивающий наибольший доход, если в производстве используется 3 типа ресурсов, запасы которых соответственно 160, 40, 200. Доход от единицы продукции 10 и 7 соответственно. Нормы расхода ресурсов заданы матрицей . Оставшийся неиспользованным второй ресурс можно реализовать по цене 2.

Обозначая объемы производства продукции , получим ограничения

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

Для анализа этого опорного плана получим общее решение:

Проанализируем опорный план на оптимальность:

Решение не оптимальное, так как увеличение  приводит к увеличению критерия, и увеличение также увеличивает критерий.

Будем увеличивать переменную , т.е. вводим ее в список базисных переменных.

При ростеx1 уменьшаются базисные переменныеx3 иx4. Определим, какая из них первая обратится в 0.

Первая обратится в 0x4 при θ =20.

Следующее опорное решение будет . Это и есть новая угловая точка.

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

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

Минимальное значение  из . Получим новое опорное решение .

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

Увеличением  улучшить критерий нельзя, любое их увеличение уменьшает критерий.

Значит, найденное нами решение является оптимальным. Значение критерия на этом решении равно 240.

3.4. Симплекс-метод в таблицах

Приведенные выше преобразования удобно выполнять в специальных таблицах, называемых симплекс-таблицами.

В симплекс-таблице выделяются следующие блоки:

Показатели критерия оптимальности (коэффициенты сj целевой функции)

Св

Бп

Шапка матрицы (наименование неизвестных)

b

коэффициенты целевой функции при базисных неизвестных

наименование базисных переменых

Текущая матрица технологических переменных

итоговый столбец (значение базисных переменнныхbi)

Оценочная строка ( оценки )

Значение целевой функции

Запишем решение задачи примера из  раздела 3.3 в симплекс-таблицах:

F

10

7

0

2

0

Св

Бп

x1

x2

x3

x4

x5

b

0

x3

4

6

1

0

0

160

2

x4

2

1

0

1

0

40

0

x5

0

8

0

0

1

200

F

-6

-5

0

0

0

80

0

x3

0

4

1

-2

0

80

10

x1

1

0.5

0

0.5

0

20

0

x5

0

8

0

0

1

200

F

0

-2

0

3

0

200

7

x2

0

1

0.25

-0.5

0

20

10

x1

1

0

-0.125

0.75

0

10

0

x5

0

0

-2

4

1

40

F

0

0

0.5

2

0

240

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

В последнюю строку первой симплекс-таблицы заносим критерий в неявной форме

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

Для оптимальности решения все оценки должны быть неотрицательны

– решение не оптимальное, т.к. есть отрицательные оценки. (-6 и -5)

Оценки могут быть вычислены по формулам (12). Произведение

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

=

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

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

– решение не оптимальное, т.к. есть отрицательная оценка -2.

- решение оптимальное, т.к. все оценки больше нуля. Очевидно, что  увеличить нельзя.

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

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

Симплекс-таблица строится для какого-либо опорного решения.

Пусть опорное решение . Симплекс-таблица для этого решения имеет вид

F

c1

c2

….

ck

cm

cm+1

cs

cj

cn

Св

Б.п

x1

x2

….

xk

xm

xm+1

xs

xj

xn

b

c1

x1

1

0

0

0

a1 m+1

a1 s

a1 j

a1 n

c2

x2

0

1

0

0

a2 m+1

a2 s

a2 j

a2 n

……

ck

xk

0

0

1

0

ak m+1

ak s

ak j

ak n

……

ci

xi

0

0

0

0

ai m+1

ai s

ai j

ai n

cm

xm

0

0

0

1

am m+1

am s

am j

am n

F

0

0

0

0

Базисная матрицаB = (A1,A2, …Am)

det B  0   B-1

Этапы симплекс-метода

  1. Проверка признака оптимальности ()
  2. Если есть ,то решение не оптимальное. Тогда выбираем столбец с минимальной оценкой. Его назовем разрешающим.
  3. Разрешающая строка выбирается по минимальному отношению свободных членов к положительным коэффициентам разрешающего столбца. Базисная переменная, выражающаяся из этой строки, выходит из списка базисных переменных. Т.е.xk выходит, аxs входит.

  1. Текущая симплекс-таблица преобразуется по следующему правилу:

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

Или новое значение элемента равно произведению элементов на главной диагонали минус произведение элементов на противоположной диагонали, и все это деленное на разрешающий элемент.

Замечание: Если в разрешающей строке был нулевой элемент, значит этот столбец не меняется; если в разрешающем столбце есть нулевой элемент, то соответствующая строка не меняется.

3.5. Варианты разрешимости задачи линейного программирования

Теорема 5: “О возможности увеличения критерия”.

Пусть  – невырожденный опорный план, существует оценка свободной переменной меньше нуля . Тогда план  не оптимальный и существует решение с лучшим значением критерия.

Для построения такого плана положим , тогда

                         (15)

Существует такое малое , что все базисные компоненты  неотрицательны, то есть решение  допустимое.

Теорема 6: “О возможности построения нового опорного плана”.

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

,

Действительно, построив план вида (15) и увеличивая , заметим, что по крайней мере одна базисная переменная  уменьшается. Когда одна из уменьшающихся базисных переменных обратится в 0, получим новый опорный план с лучшим значением критерия.

Теорема 7: “Условие неограниченности критерия”.

Если – невырожденный опорный план, существует , среди коэффициентов текущей матрицы условий нет положительных ,, то задача неразрешима из-за неограниченности критерия ().

Действительно, решение вида (15) остается допустимым при любом :

, а критерий неограниченно растет

Теорема 8: “Признак альтернативного оптимального решения”.

Пусть – невырожденный оптимальный план (выполняется признак оптимальности ,), и существует оценка свободной переменной . Тогда оптимальный план не единственный и существует другой план с таким же значением критерия , .

Действительно, на планах вида (15) критерий  не изменяется, значит, все эти планы оптимальны.

В таком случае оптимальные решения находятся на отрезке , .

3.6. Предупреждение зацикливания  симплекс-метода

Зацикливание происходит тогда, когда в одной точке пересекаются границы гиперпространств, больших, чем количество свободных переменных.

Способы предупреждения:

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

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

надо скорректировать правило выбора разрешающей строки.

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

Б.п.

x1

x2

x3

x4

x5

x6

b

x1

1

3

2

-2

0

0

6

2

1/3

x5

0

2

-6

4

1

0

4

2

0/2=0

-6/2=-3

4/2=2

x6

0

5

-15

5

0

1

10

2

0/5=0

-15/5=-3

5/5=1

F

0

-7

-2

3

0

0

50

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

Глава 4. Метод искусственного базиса

4.1. Построение начального опорного плана

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

Если матраца условий содержит единичную подматрицу, опорный план очевиден.

В случае, когда матрица условий не содержит единичной подматрицы, для поиска опорного плана строится вспомогательная задача.

Опорный план этой задачи очевиден .

Область  содержит все решения исходной задачи.

Теорема 9: Пусть  оптимальное решение расширенной задачи(4)-(6). Если все искусственные переменные , то это решение является опорным для исходной задачи. Если хотя бы одна искусственная переменная больше 0, тогда область допустимых решений исходной задачи пуста.

Вспомогательная задача всегда имеет оптимальное решение, так как функция  ограничена снизу нулем и, значит, она достигает своего минимального значения.

Пример построения начального опорного плана

Предприятие работает по трем технологиям. Найти время работы в сменах  по каждой из технологий, если в производстве используется три продукта –A,B,C. Первый и третий продукт производится, а второй расходуется. По первой технологии за одну смену производится 1 тонна продукта А, расходуется 5 тонн продукта В, производится 2 тонны продукта С. По второй технологии за смену производится 2 тонны продукта А, расходуется 5 тонн продукта В, производится 3 тонны продукта С. По третьей технологии за смену производится 1 тонна продукта А, расходуется 2 тонны продукта В, производится 1 тонна продукта С. Расход продукта В не должен превосходить 500 тонн, производство продукта А должно составить ровно 160 тонн, а производство продукта С – не менее 190 тонн. Также известен доход за смену работы по каждой технологии – 6, 7 и 2 тыс. руб. соответственно.

Математическая модель задачи после приведения её к кононическому виду запишется в следующем виде

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

Построим симплекс-таблицу для этого опорного плана.

1

1

Св

Б.п

x1

x2

x3

x4

x5

x6

x7

b

1

x6

1

2

1

0

0

1

0

160

80

0

x4

5

5

2

1

0

0

0

500

100

1

x7

2

3

1

0

-1

0

1

190

63.333

3

5

2

0

-1

0

0

350

1

x6

-1/3

0

1/3

0

2/3

1

-2/3

100/3

50

0

x4

5/3

0

1/3

1

5/3

0

-5/3

550/3

110

0

x2

2/3

1

1/3

0

-1/3

0

1/3

190/3

-1/3

0

1/3

0

2/3

0

-5/3

100/3

0

x5

-1/2

0

1/2

0

1

3/2

-1

50

0

x4

5/2

0

-1/2

1

0

-5/2

0

100

0

x2

1/2

1

1/2

0

0

1/2

0

80

0

0

0

0

0

-1

-1

0

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

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

Эти операции не реализованы в диалоговой системе решения и анализа задач линейного программированияIBLP, поэтому при использовании метода искусственного базиса вIBLP следует посмотреть на опорный план и выяснить, нет ли нулевой искусственной переменной в базисе. Если есть, то вывести её из списка базисных через блок “Базисные решения”.

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

6

7

2

Св

Б.п

x1

x2

x3

x4

x5

b

0

x5

-1/2

0

1/2

0

1

50

0

x4

5/2

0

-1/2

1

0

100

40

7

x2

1/2

1

1/2

0

0

80

160

F

-5/2

0

3/2

0

0

560

0

x5

0

0

2/5

1/5

1

70

6

x1

1

0

-1/5

2/5

0

40

7

x2

0

1

3/5

-1/5

0

60

F

0

0

1

1

0

660

оптимальное решение.

Таким образом, если работать 40 смен по первой технологии, 60 смен по второй технологии и не использовать третью технологию, то мы получим максимальный доход. При этом весь продукт В будет использован, а продукта С будет производиться на 70 тонн больше, чем запланировано.

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

Пусть имеется исходная задача (1)-(3). Тогда построим расширенную задачу:

    – сколь угодно большое число (множитель).

    – штраф за нарушение ограничений.

Теорема 10: пусть  –  оптимальное решение расширенной задачи, тогда:

Замечание: если исходная задача является задачей минимизации, критерий расширенной задачи должен иметь вид .

Пример решения задачи методом искусственного базиса

  1. Содержательное описание.

Суточная потребность человека в витаминах и минеральных веществах удовлетворяется за счет потребления двух продуктов: апельсинов и черной икры. Содержание питательных веществ в продуктах (мг/100г), суточные нормы их потребления (мг) и цена продуктов (руб/кг) задаются таблицей:

Витамины

Мин. вещества

Цена

Апельсины

2

1

100

Черная икра

1

3

200

Норма  потребления

24

27

При этом в рационе питания черной икры должно быть не более 800 грамм. Найти суточный рацион  минимальной стоимости.

  1. Математическая модель.
    1. Управляемые параметры.

x1[100г] – количество апельсинов в рационе

x2[100г] – количество икры в рационе

  1. Ограничения.

g1() – содержание витаминов в рационе

g2() – содержание икры в рационе

  1. Формулировка цели:

– стоимость рациона.

Приведем задачу к каноническому виду:

10

20

0

0

0

M

M

Св

Б.п

x1

x2

x3

x4

x5

x6

x7

b

M

x6

2

1

-1

0

0

1

0

24

24

M

x7

1

3

0

-1

0

0

1

27

9

0

x5

0

1

0

0

1

0

0

8

8

F

3M-10

4M-20

-M

-M

0

0

0

51M

M

x6

2

0

-1

0

-1

1

0

16

8

M

x7

1

0

0

-1

-3

0

1

3

3

20

x2

0

1

0

0

1

0

0

8

F

3M-10

0

-M

-M

-4M+20

0

0

19M+160

M

x6

0

0

-1

2

5

1

-2

10

2

10

x1

1

0

0

-1

-3

0

1

3

20

x2

0

1

0

0

1

0

0

8

8

F

0

0

-M

2M-10

5M-10

0

-3M+10

10M+190

0

x5

0

0

-1/5

2/5

1

1/5

-2/5

2

10

x1

1

0

-3/5

1/5

0

3/5

-1/5

6

20

x2

0

1

1/5

-2/5

0

-1/5

2/5

9

F

0

0

-2

-6

0

2-M

6-M

210

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

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

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

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

5.1. Построение двойственной задачи и ее экономическая интерпретация

Рассмотрим задачу объемного планирования. Пусть исходная задача такова:

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

bi,  – запасы ресурсов каждого вида

aij,  – нормы расходаi-го ресурса на единицуj-ой продукции

cj,  – доход от единицыj-ой продукции

Введем оценку полезности единицыi-го ресурса .

Добавим в систему одну тонну ресурса. На сколько при этом увеличится максимальный доход?

Сравним затраты ресурсов на единицуj-ой продукции с доходом, полученным от единицыj-ой продукции:

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

Тогда задача (4)-(6) являетсядвойственной к исходной задаче.

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

Пусть исходная задача имеет вид:

Тогда двойственной к задаче (7-10) называется задача вида:

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

Для применения правил, необходимо в задаче на максимум записать все ограничения – неравенства со знаком . В задаче же на минимум  –  со знаком .

  1. Количество переменных одной задачи совпадает с количеством ограничений другой задачи. Т.е. каждому ограничению одной задачи соответствует переменная другой. Ограничению-неравенству соответствует неотрицательная переменная, а ограничению-равенству – переменная произвольного знака.
  2. Правые части ограничений одной задачи являются коэффициентами критерия другой.
  3. Матрицы условий этих задач взаимно транспонированы, т.е. столбец матрицы условий одной задачи становится строкой другой.
  4. Критерий одной задачи максимизируется, а другой минимизируется. Причем в задаче на максимум все ограничения – неравенства типа , а в задаче на минимум – типа .

Пример:

Пусть исходная задача имеет вид:

Построить двойственную задачу.

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

Действительно, полученная задача совпадает с исходной.

5.2. Математические свойства пары взаимно двойственных задач

Исходная (прямая) задача

Исходная в матричном виде

Двойственная задача

Двойственная задача в матричном виде

Лемма 1: двойственная задача к  двойственной является исходной задачей.

Лемма 2 (основное неравенство теории двойственности): для любого допустимого решения прямой задачи и любого допустимого решения двойственной задачи критерий  задачи максимизации не превосходит критерия  задачи минимизации.

(7)

Доказательство:

, для него выполняются (2) и (3).

, для него выполняются (5) и (6).

Покажем, что выполняется (7). Заменяя  бóльшим значением из (5), затем  бóльшим значением из (2), получим

Теорема доказана.

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

Лемма 3 (достаточное условие оптимальности решений двух взаимно двойственных задач): решения  и  являются оптимальными для своих задач, если выполняется условие

Доказательство:

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

А это означает, что – оптимальное решение прямой задачи.

Аналогичным образом доказывается, что  – оптимальное решение двойственной задачи.

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

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

Двойственная задача

– его базисная матрица, тогда

          и его базисные компоненты можно записать в виде

,                                                             (11)

Подставим (12) в (11), получим

Неравенство (13) означает, что вектор – допустимое решение двойственной задачи

Тогда по лемме 3, если  на двух допустимых решениях  икритерии равны , то  и оптимальные решения своих задач.

Тем самым доказано, что – оптимальное решение двойственной задачи.

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

Доказательство:

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

Тогда можно сделать вывод, что .

Теорема доказана.

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

Варианты разрешимости задач двойственной пары

Вариант 1: Обе задачи разрешимы.

Построим двойственную задачу:

Вариант 2:  Критерий одной задачи не ограничен, область допустимых решений другой задачи пуста.

.

Построим двойственную задачу:

Вариант 3:  Области допустимых решений обеих задач пусты.

,  .

Построим двойственную задачу:

Таким образом, можно выделить следующие варианты разрешимости:

Следствие из первой теоремы двойственности: для разрешимости пары двойственных задач необходимо и достаточно, чтобы множество планов каждой из задач было не пустым.

Вторая теорема двойственности

Пусть взаимно двойственные задачи представлены в симметричной форме

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

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

Условия (7)-(8) не означают ничего другого, как только то, что или переменная обращается в ноль, или ограничение выполняется как равенство.

Доказательство:

Пусть имеются ,  и для них выполняются условия (7)-(8). Покажем, что это оптимальные решения своих задач.

Для этого просуммируем (7) и (8) поj и поi соответственно:

Левые части соотношений (9) и (10) равны, значит, равны и правые, а это критерии целевых функций

,  – оптимальные решения.

Пусть , – оптимальные решения. Покажем, что для них выполняются условия (7)-(8). С учетом соотношений (5) и (2) запишем

Продолжая неравенство (11) с учетом (12), получим

Так как , то каждое неравенство в (13) выполняется как равенство. Рассмотрим первое из них

Преобразуем

В левой части (14) – сумма неотрицательных слагаемых. Такая сумма равна нулю только тогда, когда каждое слагаемое равно нулю

А это и есть соотношения (7).

Аналогично доказываются и соотношения (8).

Теорема доказана.

Экономическая интерпретациявторой теоремы двойственности:

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

Соотношения (7) и (8) позволяют по оптимальному решению одной задачи найти оптимальное решение другой.

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

Следствие теоремы 2 (двойственный признак оптимальности): для того, чтобы допустимое решение задачи линейного программирования  было оптимальным, необходимо и достаточно, чтобы среди решений  системы уравнений

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

Решение  системы уравнений (15) и  удовлетворяют соотношениям (7) и (8). И если среди решений (15) есть допустимое решение двойственной задачи, то тогда выполняются все условия второй теоремы двойственности и оба эти решения будут оптимальные.

Пример:

Предприятие может работать по двум технологиям. При этом используются два типа ресурсов. Запасы ресурсов составляют 12 тонн и 4 литра соответственно. За 1 час работы по первой технологии расходуется 2 тонны первого ресурса и 1 литр второго, а за 1 час работы по второй технологии – 1 тонна первого ресурса. 1 час работы по первой технологии приносит доход 8 тыс. руб., а по второй – 3 тыс. руб. Суммарное время работы по технологиям должно составлять 6-часовую смену. Определить время работы по каждой технологии так, чтобы суммарный доход был наибольшим.

[час] – время работы по каждой технологии

Для этого запишем  соотношения дополняющей нежесткости (7-). Подставим в эти соотношения компоненты решения

Решая данную систему уравнений, получим . Подставим  в ограничения двойственной задачи. Первое ограничение не выполняется:

Мы получили, что найденное нами решение  не является допустимым для двойственной задачи. Поэтому можно сделать вывод, что решениене является оптимальным решением исходной задачи.

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

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

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

Тогда двойственная к ней будет иметь вид:

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

.

Изучим влияние пока только одного параметра – ветора  на оптимальное решение .

Пусть правые части ограничений (ресурсы) меняются, получая малые приращения:

– возмущенный вектор правых частей ограничений.

– (малые) приращения ресурсов.

Тогда задача с новым вектором правых частей ограничений (возмущенная задача)I’ и двойственная к нейII’ запишутся в виде

I’.                                              (6)

II’.

Как найти оптимальное решение задачиI’, зная оптимальное решение задачиI?

Лемма: пусть – невырожденное оптимальное решение задачиI и базисная матрица этого плана.

Если выполняется условие

,

то:

          .

Доказательство:

Пусть  – оптимальное решение, его базисная матрица. Значит, существует и обратная матрица , базисные компоненты оптимального плана –,выполняется признак оптимальности.

Покажем, что вектор (10) – оптимальное решение возмущенной задачи.

Сначала покажем, что это допустимое решение, то есть для него должны выполняться ограничения (7) и (8).

Подставляя  в левую часть (7), получим

то есть ограничение (7) выполняется.

Условие (8) выполняется из условия (9) леммы.

Итак,допустимое решение задачиI’.

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

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

Первая часть леммы доказана.

Справедливость второй части (11) следует из того, что формулы расчета оптимальных решений задач, двойственных кI иI’ задач также совпадают.

Лемма доказана.

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

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

Доказательство:

Рассмотрим оптимальное значение критерия как функцию от правых частей ограничений

По первой теореме двойственности критерии на оптимальных решениях прямой и двойственной задач равны

Будем рассматривать малые приращения правых частей ограничений, лежащие в области устойчивости двойственных оценок , тогда по доказанной выше лемме решение двойственной задачи не меняется  и в правой части ( )bi – переменные, аyi– константы.

Возьмем производную поbi от левой и правой части ( ), получим

Это и есть соотношение (15).

Теорема доказана.

Экономическая интерпретация третьей теоремы двойственности

Если соотношение (15) выполняется, то .

То есть если ресурс изменился на 1 , то .

Из соотношения (17) следует, что компонента  оптимального решения двойственной задачи показывает, на сколько изменится оптимальное значение критерия при увеличении ресурса на 1.

Двойственные переменные  называют также двойственными оценками, модельными ценами, теневыми ценами.

Разлагая функцию оптимального значения критерия в ряд по формуле Тейлора в окрестности  , получим

В области устойчивости двойственных оценок приращение критерия может быть получено по формуле (18)

Пример:

Для задачи из раздела 5.2 о работе предприятия по двум технологиям, определим, как изменится оптимальное решение при изменении объемов используемых ресурсов

Математическая модель задачи:

Найдем оптимальное решение этой задачи методом искусственного базиса.

Для этого строим расширенную задачу:

Решение в симплекс-таблицах:

F

8

3

-M

Св

Бп

x1

x2

x3

x4

x5

b

0

x3

2

1

1

0

0

12

0

x4

1

0

0

1

0

4

-M

x5

1

1

0

0

1

6

F

-8-M

-3-M

0

0

0

-6M

0

x3

0

1

1

-2

0

4

8

x1

1

0

0

1

0

4

-M

x5

0

1

0

-1

1

2

F

0

-3-M

0

8+M

0

-2M+32

0

x3

0

0

1

-1

-1

2

8

x1

1

0

0

1

0

4

3

x2

0

1

0

-1

1

2

F

0

0

0

5

3+M

38

Ранее было найдено оптимальное решение двойственной задачи:

Найти оптимальное решение данной задачи, если вектор ресурсов изменился:

,

Базисная матрица оптимального плана

Обратную к ней возьмем из оптимальной симплекс-таблицы под единичной матрицей исходной симплекс-таблицы

Св

Бп

x1

x2

x3

x4

x5

x6

b

0

x3

0

0

1

2

8

x1

1

0

0

4

3

x2

0

1

0

2

F

0

0

0

Проверим, что эти матрицы взаимно обратные:

Базисные компоненты  решения измененной задачи

неотрицательны, значит по лемме 3 это базисные компоненты оптимального плана измененной задачи

В новых условиях по первой технологии следует работать 5 часов, по второй – 3 часа. Останется неиспользованной одна тонна первого ресурса.

Приращение оптимального значения критерия

Доход на новом оптимальном плане

Построение областей устойчивости двойственных оценок

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

Для рассмотренной задачи найдем интервал устойчивости двойственных оценок к изменению запаса второго ресурса:

Получили интервал устойчивости в приращениях

,

А непосредственно интервал устойчивости

Это означает, что при уменьшении запасов второго ресурса до нуля или увеличении до 6 оценки всех ресурсов сохранят свои значения , а приращение критерия можно найти по формуле

Построим область устойчивости двойственных оценок к изменению всех ресурсов.

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

Область устойчивости   определяется условиями

Подставляем сюда

Для приращений ресурсов получаем систему неравенств

Неравенства (1) и определяют область устойчивости  в трехмерном пространстве приращений ресурсов.

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

Пусть меняется только второй ресурс:

– интервал устойчивости двойственных оценок  к изменению второго ресурса.

Пусть меняется только третий ресурс:

– интервал устойчивости двойственных оценок  к изменению третьего ресурса.

Построим область устойчивости двойственных оценок к одновременному изменению второго и третьего ресурсов:

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

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

Пусть

Тогда приращение оптимального значения критерия

Базисные компоненты оптимального решения

,

а полный вектор нового оптимального решения

Экономическая интерпретация полученного решения:

При уменьшении запасов второго ресурса (катализатора) на 2 литра и одновременном увеличении длительности рабочей смены на 3 часа, по первой технологии следует работать 2 часа, по второй – 7 часов, при этом максимально возможный доход составит 37 тысяч рублей. Тонна первого ресурса останется неиспользованной.

5.4. Определение оптимального решения двойственной задачи из оптимальной симплекс-таблицы прямой

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

Оптимальное решение  получено симплекс-методом, – базисная матрица оптимального решения.

Оптимальное решение двойственной задачи (по первой теореме двойственности)

,

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

Подставляя (4) в (5) получим

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

выводим из (6) важное свойство оценок :

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

Из соотношения (6) легко найти компоненты оптимального решения двойственной задачи.

Действительно, пусть  – единичный вектор с единицей вi-ой строке. В исходной симплекс-таблице всегда есть такие вектора.

Оценка  переменной  согласно (6) запишется

,

откуда

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

Пример:

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

Воспроизведем для наглядности решение симплекс-методом

F

8

3

0

0

-M

Св

Бп

x1

x2

x3

x4

x5

b

0

x3

2

1

1

0

0

12

0

x4

1

0

0

1

0

4

-M

x5

1

1

0

0

1

6

F

-8-M

-3-M

0

0

0

-6M

0

x3

0

1

1

-2

0

4

8

x1

1

0

0

1

0

4

-M

x5

0

1

0

-1

1

2

F

0

-3-M

0

8+M

0

-2M+32

0

x3

0

0

1

-1

-1

2

8

x1

1

0

0

1

0

4

3

x2

0

1

0

-1

1

2

F

0

0

0

5

3+M

38

3, 4, 5.

Оптимальное решение двойственной задачи будет находиться в строке оценок оптимальной симплекс-таблицы под единичной матрицей исходной симплекс-таблицы:

5.5. Двойственный симплексный метод

Рассмотрим базисное недопустимое решение .

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

Для этого решения

, . А это означает, что псевдо-план исходной задачи соответствует опорному плану двойственной задачи: . При этом каждому псевдо-плану исходной задачи соответствует угловая точка двойственной.

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

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

Если симплексный метод – метод последовательного улучшения плана (улучшаются планы ), то двойственный симплекс-метод – метод последовательного улучшения оценок (улучшаются решения двойственной задачи – двойственные оценки ).

Условия применимости двойственного симплекс-метода:

Итерации в двойственном симплекс-методе выполняются по следующим правилам:

Это правило гарантирует, что новое базисное решение будет псевдо-планом.

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

Пример:

  1. Содержательное описание.

Целлюлозно-бумажный комбинат (ЦБК) на берегу озера Байкал может работать по двум технологическим режимам. По первому режиму в течение смены расходуется 100 м3 древесины, производится 50 тонн целлюлозы, 60 центнеров лигнитов (вещества, используемые в химической промышленности) и сбрасывается в озеро 10 кг отравляющих веществ. По второму режиму в течение смены расходуется 120 м3 древесины, производится 75 тонн целлюлозы, 30 центнеров лигнитов, сбрасывается в озеро 25 кг отравляющих веществ. Годовой план производства составляет 15000 тонн целлюлозы, 1200 тонн лигнитов. Предельные годовые нормы выброса отравляющих веществ составляют 5 тонн. Определить годовой план работы ЦБК, требующий минимального расхода древесины.

  1. Математическая модель.
    1. Управляемые параметры.

[см] – время работы (в сменах) по первой технологии;

[см] – время работы (в сменах) по второй технологии;

– годовой план работы.

2.2 Ограничения.

годовое производство целлюлозы в тоннах должно быть не меньше плана;

годовое производство лигнитов в центнерах должно быть не меньше плана;

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

время работы по каждой из технологий неотрицательно

  1. Формулировка цели.

годовой расход древесины должен быть минимален.

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

                                          (1)

Приведем её к каноническому виду

– очевидное базисное решение, но оно не является допустимым.

Обеспечим условия применения двойственного симплекс-метода. Сменим знаки левых и правых частей первых двух уравнений

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

100

120

0

0

0

Св

Бп

x1

x2

x3

x4

x5

b

0

x3

-50

-75

1

0

0

-15000

0

x4

-60

-30

0

1

0

-12000

0

x5

10

25

0

0

1

5000

F

-100

-120

0

0

0

0

120

x2

2/3

1

-1/75

0

0

200

0

x4

-40

0

-2/5

1

0

-6000

0

x5

-20/3

0

1/3

0

1

0

F

-20

0

-8/5

0

0

24000

120

x2

0

1

-1/50

1/60

0

100

100

x1

1

0

1/100

-1/40

0

150

0

x5

0

0

2/5

-1/6

1

1000

F

0

0

-7/5

-1/2

0

27000

– псевдо-план.

На первой итерации выбирается первая разрешающая строка (-15000<0) и второй разрешающий столбец (120/75<100/50). Выполняются операции однократного замещения. Получаем следующее приближение к области.

На второй итерации разрешающая строка вторая (-6000,0), разрешающий столбец первый (20/40=0.5< 8/5:2/5=4).

Следующее решение

– допустимое базисное, значит оптимальное.

Экономическая интерпретация полученного решения: для обеспечения минимального расхода древесины нужно работать 150 смен по первой технологии, 100 смен по второй технологии, при этом расход древесины будет составлять 27000 м3. Производство целлюлозы и лигнитов совпадает с плановым (так какx3=x4=0), выброс отравляющих веществ на 1000 кг меньше предельно-допустимых норм выброса.

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

                                         (3)

Введем переменные двойственной задачи:

– оценка полезности 1 тонны целлюлозы;

– оценка полезности 1 центнера лигнитов;

– оценка «полезности» 1 кг отравляющих веществ. Значениеу3 на оптимальном плане будет показывать, на сколько изменится критерий при увеличенииb3на единицу (с -5000 до -4999). В терминах исходной задачи  – это приращение расхода древесины от ужесточения (уменьшения) предельно допустимых норм выброса отравляющих веществ на один килограмм.

Тогда двойственная задача запишется в виде

        (4)

Найдем оптимальное решение двойственной задачи из оптимальной симплекс-таблицы прямой задачи:

                               (5)

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

Действительно, (5) – это не оптимальное решение задачи (4), двойственной к задаче (3). Вектор  – это оптимальное решение задачи, двойственной к задаче (2). Именно эта задача представлена в исходной симплекс-таблице.

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

Построим двойственную задачу к задаче (2):

       (6)

После  замены переменных

задача (6) обращается в задачу (4).

Таким образом, если из симплекс-таблицы получено оптимальное решение

задачи,  двойственной к задаче (2), то решение двойственной к  задаче (3) может быть получено сменой знаков компонент решения:

Экономический смысл двойственных переменных:

показывает, что при увеличении плана выпуска целлюлозы на 1 тонну расход древесины возрастет  на 1.4 м3.

показывает, что при увеличении плана выпуска лигнитов  на 1 центнер расход древесины возрастет  на 0.5 м3.

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

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

Глава 6. Послеоптимизационный анализ задачи линейного программирования

Пусть исходная задача решена, получено её оптимальное решение и оптимальное решение двойственной к ней задачи:

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

Послеоптимизационный анализ предполагает решение следующих задач:

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

I.

Двойственная к ней будет иметь вид

II.

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

Рассмотрим другие виды анализа.

6.1. Добавление нового ограничения

Пусть в математической модели задачи (1-3) появилось новое ограничение

Возможны две ситуации:

Для этого требуется новое ограничение привести к виду уравнения.

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

Пример:

В задаче о работе ЦБК учтем ограничения на кислотные выбросы в атмосферу. Известно, что по первой технологии за 1 смену выбрасывается 1 кг кислотных выбросов, по второй – 3 кг. При этом предельно допустимые годовые нормы выброса составляют 360 кг.

В математической модели появится новое ограничение

а вся система ограничений примет вид

Проверим, удовлетворяет ли прежнее оптимальное решение  новому ограничению:

Ограничение не выполняется.

Преобразуем его к виду уравнения, введя балансовую переменнуюx6

Заменим в этом уравнении базисные переменныеx1,x2 их значениями через свободные из оптимальной симплекс-таблицы

Уравнение примет вид

Включаем его в оптимальную симплекс-таблицу и решаем далее двойственным симплекс-методом

100

120

Св

Бп

x1

x2

x3

x4

x5

x6

b

120

x2

0

1

-1/50

1/60

0

0

100

100

x1

1

0

1/100

-1/40

0

0

150

0

x5

0

0

2/5

-1/6

1

0

1000

0

x6

0

0

1/20

-1/40

0

1

-90

F

0

0

-7/5

-1/2

0

0

27000

120

x2

0

1

1/75

0

0

2/3

40

100

x1

1

0

1/25

0

0

-1

240

0

x5

0

0

1/15

0

1

-20/3

1600

0

x4

0

0

-2

1

0

-40

3600

F

0

0

-12/5

0

0

-20

28800

На следующей итерации получаем новое оптимальное решение

В новых условиях комбинат должен работать 240 смен по первой технологии, 40 смен по второй. Расход древесины возрастет до28800 м3.

6.2. Добавление новой переменной

Пусть в математической модели (1-3) появилась новая переменная

В задаче объемного планирования это означает возможность производить новый вид продукции с известными затратами ресурсов и известным доходом от единицы продукции. Сохранится ли прежнее оптимальное решение? Если нет, то как найти новое оптимальное решение?

Если в исходной задаче появляется новая переменная, то в двойственной задаче появляется новое ограничение

          (6)

или

Вектор – прежнее оптимальное решение с нулевойn+1-ой компонентой является допустимым решением новой задачи (1’-3’). Если выполняется условие (6), то вектор  – прежний вектор оптимальных двойственных оценок – допустимое решение двойственной к (1’-3’) задачи. Соотношения дополняющей нежесткости для этих двух решений пополнились условием

и выполняются за счет . Значит, решение  – оптимальное для новой задачи.

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

Если ограничение (6) не выполняется, затраты на единицу новой продукции меньше дохода, , то такую продукцию следует производить, объем производства нужно увеличивать.

Для получения нового оптимального решения следует дополнить прежнюю оптимальную симплекс-таблицу новым столбцом

а оценку переменной  найти как разность левой и провой части ограничения  (6) двойственной задачи

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

Пример:

Предположим, что у ЦБК появилась возможность работать по третьей технологии с расходом за смену 103 кубометра древесины, производительностью в смену 60 тонн целлюлозы, 40 центнеров лигнитов и 20 килограммов отравляющих веществ.

, .

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

                          (7)

Новая переменная порождает в двойственной задаче новое ограничение

                            (8)

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

Ограничение (8) не выполняется, суммарная оценка полезности произведенной за смену продукции (104 м3) превышает затраты (103м3), значит прежнее решение не является оптимальным.

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

В исходную симплекс-таблицу новый вектор условий войдет в виде

, так как менялись знаки в первых двух уравнениях (см. раздел 5.5). В оптимальной симплекс-таблице он преобразуется к виду

Оценка переменной  определится как разность левой и правой части ограничения двойственной задачи (8)

Оценка положительна, что нарушает условие оптимальности опорного плана. Решаем далее симплекс-методом

Исходная симплекс-таблица

100

120

0




Похожие работы, которые могут быть Вам интерестны.

1. Курс лекций по социологии

2. Экологическое почвоведение курс лекций

3. Экономика в строительстве курс лекций

4. ФИНАНСОВО – ИНВЕСТИЦИОННЫЙ АНАЛИЗ КУРС ЛЕКЦИЙ

5. Финансовый риск-менеджмент курс лекций

6. Валютный курс. Валютная котировка (методы валютной котировки). Виды курсов. Режимы валютных курсов. Режим валютного курса в России. Как устанавливается валютный курс в РФ

7. Анализ прямых расходов предприятия и методы их оптимизации

8. Методы оптимизации управляющих программ, позволяющие сократить время обработки деталей на оборудовании с ЧПУ

9. Мікроекономіка курс лекцій

10. Английский язык Вводно-коррективный курс