Линейное программирование. Методы нелинейной оптимизации

Размещено на http://allbest.ru

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

Государственное образовательное учреждение высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского»

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

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

Курс лекций

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

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

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

2010



Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.3 Изменение коэффициентов критерия

6.4 Изменение технологических коэффициентов

7. Классическая теория оптимизации

7.1 Необходимые условия оптимальности

7.2 Достаточные условия оптимальности

8. Нелинейное программирование

8.1 Задачи на условный экстремум. Метод множителей Лагранжа

8.2 Задачи выпуклого программирования

Литература

Введение

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



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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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

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

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

· Задачи динамического программирования - задачи, в которых применяются пошаговые методы решения.

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

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



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

· Теория управления запасами изучает задачи определения объемов поставки и сроков хранения продукции.

· Сетевое планирование и управление предлагает методы планирования работ, связанных сетевыми графиками.

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

Задача объемного планирования.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

при условии

Задача о диете

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

при условии

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

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

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



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

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

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

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

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

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



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

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

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

· Каноническая

· Симметричная

· Общая.

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

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

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

() = (*) >

=

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

=

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

= ( )

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

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

() = (*)

+ + …+ =

,

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

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



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

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

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

Приведение задачи линейного программирования от одной эквивалентной формы к другой.

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

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

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



·

+ =

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

·

- =

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

= -

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

= +



Переход от уравнений к неравенствам:

· Если имеется уравнение:

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

· Пусть есть несколько ограничений:

А также:

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



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

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

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

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

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

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

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

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



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

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

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



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

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

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

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

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

Линия уровня - это множество точек, в которых функция принимает постоянные значения.

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

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

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

= = ()

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

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

· Градиент функции, вычисленный в точке, перпендикулярен линии уровня функции, проходящей через эту точку.

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

Пример:



=

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

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

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

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

Пример:

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

·

·

·

·

- оптимальное решение двумерной задачи, в пространстве x₂,x₄.

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

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

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

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

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

· Это всегда многоугольник (многогранник в пространстве более двух переменных).

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



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

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

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

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

ш

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

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

, ,

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

,



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

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

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

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

Пусть ,.



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

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

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

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

, , , ,

,

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

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

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

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

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



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

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

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

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

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

Вектора линейно-зависимые, если (для трех векторов)

;

либо если определитель из этих векторов равен нулю.



Пример:

·

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

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

·

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

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

·

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



·

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

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

· - базисное решение.

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

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

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

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

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

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



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

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

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

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

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

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



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

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



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

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

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

гранник

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

Размещено на http://allbest.ru

- тетраедр

Размещено на http://allbest.ru

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

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

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

2. Проверяется признак оптимальности решения.

3. Построение нового опорного решения - переход от одной вершины симплекса к другой .

4. l=l+1, повторять со второго пункта до тех пор, пока не выполнятся условия оптимальности.

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

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

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

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



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

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

,

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

,

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



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

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

Для

т.к. , то и .

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

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

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

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

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

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

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

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

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

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



Размещено на http://allbest.ru

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

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

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

Первая обратится в 0 x₄ при и =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

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

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



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

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

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

=

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

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

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

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

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

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

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



Базисная матрица B = (A₁, A₂, … A_m)

det B 0 B^-1

· при базисных переменных текущая матрица единичная.

· любой столбец .

· вектор правых частей ограничений .

· оценки при свободных переменных не нулевые

.

· в правой нижней клетке - значение критерия



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

1. Проверка признака оптимальности ()

2. Если есть , то решение не оптимальное. Тогда выбираем столбец с минимальной оценкой. Его назовем разрешающим.

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

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

· разрешающая строка делится на разрешающий элемент:

· разрешающий столбец заменяется единичным.

· все остальные элементы симплекс-таблицы могут быть пересчитаны по правилу четырехугольника:

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

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

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

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

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

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

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



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

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

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

,

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

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

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

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

,



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

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

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

, .

Действительно, на планах критерий

не изменяется, значит, все эти планы оптимальны.

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

, .

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

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

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

· придать малые приращения каждому ограничению

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

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

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

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

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



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 тыс. руб. соответственно.

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· если расширенная задача неразрешима из-за неограниченности критерия, то и исходная задача неразрешима из-за неограниченности критерия.

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

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

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

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

	Витамины	Мин. вещества	Цена
Апельсины	2	1	100
Черная икра	1	3	200
Норма потребления	24	27

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

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

Управляемые параметры.

x₁[100г] - количество апельсинов в рационе

x₂[100г] - количество икры в рационе

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

g₁() - содержание витаминов в рационе

g₂() - содержание икры в рационе

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

4.

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

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



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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



Тогда двойственной к задаче называется задача вида:

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

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

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

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

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

4. Критерий одной задачи максимизируется, а другой минимизируется. Причем в задаче на максимум все ограничения - неравенства типа , а в задаче на минимум - типа .

Пример:

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

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

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



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

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

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

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

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

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



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

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

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

,

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

Размещено на http://allbest.ru

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

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

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

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

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

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

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

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

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

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



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

· По теореме 4 выполняется признак оптимальности

,

· Покажем, что оптимальное решение двойственной задачи может быть найдено в виде

Подставим и получим

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

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



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

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

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

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

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

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

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

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

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



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

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

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



.

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

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

, .

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



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

1.

2.

3.

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

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

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



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

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

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

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

· Достаточность:

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

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

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



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

· Необходимость:

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

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

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

Преобразуем



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

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

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

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

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

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

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

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

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

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

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

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

...