Учебно-методический комплекс (стр. 17 )

Теперь мы готовы сформулировать основной результат.

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

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

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

(1.12)

(1.13)

(1.14)

(1.15)

(1.16)

(1.17)

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

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

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

Определение 11. Квадратичная форма называется положительно(отрицательно)-определенной, если для всех значений переменных, кроме .

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

Справедлива

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

Определение 13. Задача, состоящая в определении максимального (минимального) значения функции

(1.18)

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

(1.19)

(1.20)

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

Для сформулированной задачи квадратичного программирования (1.18)-(1.20) функция Лагранжа запишется в виде

Если лагранжианимеет седловую точку , то в этой точке выполняются соотношения (1.12)-(1.17). Вводя теперь дополнительные неотрицательные переменные и обращающие неравенства (1.12) и (1.15) в равенства, перепишем выражения (1.12)-(1.17) для задачи квадратичного программирования следующим образом:

(1.21)

(1.22)

(1.23)

(1.24)

(1.25)

Таким образом, чтобы найти решение задачи квадратичного программирования (1.18)-(1.20), нужно определить неотрицательное решение систем линейных уравнений (1.21) и (1.22), удовлетворяющее условиям (1.23) и (1.24).

Пример 5. Найдем максимальное значение функции

при условиях

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

и запишем в виде выражений (1.21)-(1.25) необходимые и достаточные условия существования седловой точки построенной функции:

(1.26)

(1.27)

(1.28)

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

Задание. Проделайте все необходимые вычисления в примере 5 и убедитесь в правильности предъявленного решения.

Исследуйте самостоятельно следующие задачи:

а)

б)

в)

г)

Задачи линейного программирования

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

Термин “программирование” – не совсем удачный перевод английского слова "programming", которое правильнее перевести как "планирование", что объясняется областью применения этой дисциплины. Методы линейного программирования оказались весьма эффективными при решении многих экономических задач, возникающих в производстве, торговле, управлении финансами, когда целью является максимизация или минимизация некоторого экономического показателя (максимизация прибыли или объема выпуска продукции, минимизация затрат сырья или транспортных расходов).

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

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

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

Найти максимум (или минимум) линейной функции

(2.1)

от переменных удовлетворяющих линейным ограничениям в форме равенств или неравенств

(2.2)

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

(обычно записывают так: ). (2.3)

Договоримся о терминологии линейного программирования. Функция носит название целевой функции. Её коэффициенты образуют вектор называемый целевым вектором. Любой вектор координаты которого удовлетворяют условиям (2.2), (2.3), называется допустимым планом (допустимым вектором, допустимой точкой) задачи линейного программирования. Все они образуют множество допустимых планов задачи. План доставляющий целевой функции наибольшее (или наименьшее) значение, называется оптимальным планом задачи ЛП. Ограничения (2.2) будем называть основными ограничениями, правая их часть – вектор – называется вектором ограничений или вектором ресурсов (запасов). Коэффициенты левых частей основных ограничений составляют матрицу , которую мы будем называть технологической матрицей.

Примеры моделей ЛП

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

В качестве примера рассмотрим две задачи.

Задача о производстве красок. Небольшая фабрика изготовляет два вида красок: INT для внутренних работ и EXT – для наружных работ. В производстве красок используются два исходных продукта А и В. Из-за малой площади склада максимально возможные суточные запасы этих продуктов равны 6 т. и 8 т. соответственно. На производство 1 т. краски INT расходуется 1 т. продукта А и 2 т. продукта В, а на изготовление 1 т. краски EXT идет 2 т. продукта А и 1 т. продукта В. Фабрика продает краску по цене 3 тыс. дол. за тонну краски INT и 2 тыс. дол. за тонну краски EXT. Исходные данные удобно свести в таблицу.

Исходные продукты	Расход продукта на 1 т. краски	Запас продуктов
INT	EXT
А	1	2	6
В	2	1	8
Цена 1 т. краски	3 тыс. дол.	2 тыс. дол.

Изучение рынка сбыта показало, что суточный спрос на краску EXT никогда не превышает спрос на краску INT, более чем на 1 т. Какое количество краски каждого вида должна производить фабрика в сутки, чтобы доход от реализации продукции был максимален?

Построим математическую модель задачи. Для этого надо определить переменные задачи, целевую функцию и ограничения, которым удовлетворяют переменные. Обозначим через планируемый суточный объем производства краски INT, а через суточный объем производства краски EXT. Целевая функция будет выражать суточный доход от продажи краски, равный (тыс. долл.). Этот доход подлежит максимизации.

Построим ограничения задачи, связанные с ограниченными запасами продуктов А и В. На производство краски INT в количестве (т) будет использовано (т) продукта А, а на производство краски EXT в объеме (т) будет затрачено (т) продукта А. Поскольку суточный запас продукта А равен 6 т., то расход продукта А на изготовление красок двух видов не может превышать в сутки этой величины: Аналогично получим ограничение, связанное с запасом продукта В: Ограничение по соотношению спроса на краски можно описать неравенством: Учитывая естественные условия неотрицательности объемов выпуска продукции, окончательно получим следующую задачу линейного программирования:

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

Питательные вещества	Кол-во единиц питат. в-ва в 1 кг корма	Норма вхождения пит-х в-в в рацион
сено	силос
	3	1	9
	1	2	8
	1	6	12
Стоимость 1 кг корма	5 руб.	4 руб.

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

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

– по веществу :

– по веществу :

– по веществу :

При этом переменные не могут принимать отрицательные значения:

Различные формы записи задачи ЛП

Кроме развернутого представления задачи ЛП в виде (2.1)-(2.3) применяются и другие формы ее записи.

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

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

где – план задачи ЛП, – целевой вектор, – вектор запасов, – технологическая матрица.

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

Задание. Запишите задачу о производстве красок и задачу о рационе скота в векторно-матричной форме. Составьте задачи ЛП для процессов, описанных в пособии "Математическое программирование", часть 1, №№ 1.159; 1.161; 1.169; 1.173; 1.184; 1.187.

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

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

Каноническая задача ЛП формулируется следующим образом. Требуется найти максимум линейной функции

(2.4)

от переменных удовлетворяющих линейным ограничениям-равенствам

(2.5)

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

. (2.6)

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

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

Стандартная задача ЛП отличается от канонической только типом основных ограничений. Все они должны иметь форму неравенств "": найти максимум линейной функции

(2.7)

от переменных удовлетворяющих линейным ограничениям-неравенствам

(2.8)

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

. (2.9)

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

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

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

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

Эквивалентные преобразования задач ЛП

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

Ограничение-неравенство сводится к ограничению вида "" умножением на "–1":

Стандартное ограничение можно привести к каноническому в форме равенства с помощью следующего приема. Обозначим через разность правой и левой частей неравенства:

(2.10)

Очевидно, что Условие (2.10) можно переписать в форме канонического ограничения-равенства Другими словами, ограничение-неравенство вида "" сводится к равенству путем добавления в левую часть новой (дополнительной) неотрицательной переменной.

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

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

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