Основы математического программирования

Тема 2. Основы математического программирования Вопросы 1. Классификация моделей математического программирования. 2. Линейное программирование (ЛП). Геометрическая интерпретация задачи ЛП. 3. Нелинейное программирование. Литература 1. Лунгу К. Н. Линейное программирование. Руководство к решению задач. - М.: ФИЗМАТЛИТ, 2005.  2. Кремер Н.Ш. Исследование операций в экономике: Учеб. пособие для вузов /Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2005. 3. Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. 4. Шикин Е.В., Чхартишвили А.Г.. Математические методы и модели в управлении. - М.: Издательство «Дело», 2000. Введение Характерной чертой большинства экономических задач является множественность решений, т.е. множественность возможных вариантов. Существует два принципа выбора: волевой и критериальный. Волевой выбор при современных масштабах производства, усложненных экономических связях между различными отраслями народного хозяйства, сложной технологии часто приводит к огромным потерям в экономике. Критериальный выбор заключается в том, что принимается некоторый критерий и сравниваются возможные варианты по этому критерию. Применительно к хозяйственному объекту в качестве критерия могут выступать ресурсов, или минимум затрат на ее производство, или максимум прибыли от реализации. Принимается наилучший вариант с точки зрения выбранного критерия. Наилучший по латыни optimus, отсюда наилучшее решение называется оптимальным, а задача принятия оптимального решения - задачей оптимизации. В рамках данной лекции рассмотрена общая классификация моделей математического программирования и такие разделы математического программирования как линейное программирование и нелинейное программированное. Вопрос 1. Классификация моделей математического программирования. 1.1 Математическая постановка задачи оптимизации Математической постановке задачи оптимизации предшествует ее содержательная постановка. Задача формулируется заказчиком, т.е. лицом, заинтересованном в ее решении. Выделяется цель задачи, рассматриваются условия ее решения (исходные данные), требования, предъявляемые к результатам. Математические методы по своей природе неприменимы к содержательной формулировке задачи, поэтому следующий этап - математическая постановка задачи, в ходе которой строится ее математическая модель. Математическая модель предназначается для описания содержательной постановки задачи с помощью математических символов. При рассмотрении ЭММ оперируют следующими понятиями: критерий оптимальности, целевая функция, система ограничений, уравнения связи, решение модели. Критерием оптимальности называется некоторый показатель, имеющий экономическое содержание, служащий формализацией конкретной цели управления и выражаемый при помощи целевой функции через факторы модели. Критерий оптимальности определяет смысловое содержание целевой функции. Целевая функция математически связывает между собой факторы модели, и ее значение определяется значениями этих величин. Не следует смешивать критерий оптимальности и целевую функцию. Так, например, критерий прибыли и критерий стоимости произведенной продукции могут описываться одной и той же целевой функцией: , где  - номенклатура производимой продукции; xj - объем выпуска j-й номенклатуры; cj - прибыль от выпуска единицы j-й номенклатуры или стоимость единицы j-й номенклатуры в зависимости от смысла критерия оптимальности. Система ограничений определяет пределы, сужающие область осуществимых, приемлемых или допустимых решений и фиксирующие основные внешние и внутренние свойства объекта. Ограничения определяют область протекания процесса, пределы изменения параметров и характеристик объекта. Уравнения связи являются математической формализацией системы ограничений. Между понятиями "система ограничений" и "уравнения связи" существует точно такая же аналогия, как и между понятиями "критерий оптимальности" и "целевая функция": различные по смыслу ограничения могут описываться одинаковыми уравнениями связи, а одно и то же ограничение в разных моделях может записываться различными уравнениями связи. Таким образом, именно критерий оптимальности и система ограничений в первую очередь определяют концепцию построения будущей математической модели, т.е. концептуальную модель, а их формализация, т.е. целевая функция и уравнения связи, представляет собой математическую модель. Решением математической модели называется такой набор (совокупность) значений переменных, который удовлетворяет ее уравнениям связи. Решения, имеющие экономический смысл, называются структурно допустимыми. Модели, имеющие много решений, называются вариантными в отличие от безвариантных, имеющих одно решение. Среди структурно допустимых решений вариантной модели, как правило, находится одно решение, при котором целевая функция в зависимости от смысла модели имеет наибольшее или наименьшее значение. Такое решение, как и соответствующее значение целевой функции, называется оптимальным (в частности, наибольшим или наименьшим). В общем случае задача оптимизации может быть записана следующим образом: найти максимальное (минимальное) значение целевой функции: (2) (1) при ограничениях в виде равенств или неравенств (2) и условий неотрицательности переменных . (3) Предполагается, что функция i и f известны, а bi - заданные постоянные. В каждом из ограничений (2) сохраняется только одни знак , = или . Суть такой постановки задачи заключается в следующем: необходимо определить такие неотрицательные значения x1, x2, ..., xn, которые удовлетворяли бы ограничениям (2) и при этом придавали бы целевой функции (1) искомое оптимальное значение. Комплекс специальных методов, обеспечивающих в условиях множества возможных решений выбор такого, которое является наилучшим (оптимальным) по заданному критерию при определенных ограничительных условиях называется математическим программированием. Математическое программирование - действенный инструмент эффективного решения задач управления. Название указанного комплекса методов обусловлено тем, что в процессе их использования получаются оптимальные решения, но для выхода на такое решение необходимо выполнить ряд действий по определенной программе. Задачи математического программирования чрезвычайно разнообразны. Они могут встречаться почти в любой области человеческой деятельности: в экономике, технике, в научных исследованиях. 1.2 Краткая классификация методов математического программирования В зависимости от особенностей целевой функции z(x) и функций, задающих ограничения i (x), задачи математического программирования делятся на ряд типов. Если целевая функция Z=z(x) и функции i (x) , входящие в систему ограничений, линейны (первой степени) относительно входящих в задачу неизвестных xj, то такой раздел математического программирования называется линейным программирование (ЛП). Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т.д. Если в задаче математического программирования целевая функция z(x) и (или) хотя бы одна из функций систем ограничений i (x) нелинейна, то такой раздел называется нелинейным программированием (НЛП). Методы и модели нелинейного программирования могут применяться при решении перечисленных выше задач, когда хотя бы одна из функций z(x), i (x) нелинейна. Если на все или некоторые переменные xj наложено условие дискретности, например целочисленности (xj=0, 1, 2...), то такие задачи рассматриваются в разделе математического программирования, называемом дискретным, в частности целочисленным (ЦП), программированием. Методами ЦП решается широкий круг задач оптимизации с неделимостями, комбинаторного типа, с логическими условиями и т.д. В частности, задачи выбора (о назначениях), о контейнерных перевозках (о рюкзаке), о маршрутизации (коммивояжера), теории расписаний, комплектных поставок и комплектования, размещения производственно-складской структуры и т.п. Если параметры целевой функции и (или) системы ограничений изменяются во времени или сам процесс выработки решения имеет многошаговый характер, то такие задачи решаются методами динамического программирования (ДП). Методами ДП могут решаться задачи перспективного и текущего планирования, управления производством, поставками и запасами в условиях изменяющегося спроса, распределения ограниченных ресурсов, в частности размещения капитальных вложений, замены оборудования и т.д. В перечисленных выше разделах математического программирования предполагается, что вся информация о протекании процессов заранее известна и достоверна. Такие методы оптимизации называются детерминированными или методами обоснования решений в условиях определенности. Если параметры, входящие в функцию цели, или ограничения задачи являются случайными, недостоверными величинами или если приходится принимать решения в условиях риска, неполной или недостоверной информации, то говорят о проблеме стохастической оптимизации, а соответствующий раздел называется стохастическим программированием (СП). К нему в первую очередь следует отнести методы и модели выработки решений в условиях конфликтных ситуаций (математическая теория игр), в условиях неполной информации (экспертные оценки), в условиях риска (статистические решения) и др. Позднее появились другие типы задач, учитывающих специфику целевой функции и системы ограничений, в связи с чем возникли параметрическое, дробно-линейное, блочное, сетевое (потоковое), многоиндексное, булевское, комбинаторное и другие типы программирования. В случае нелинейностей специфика задач породила квадратичное, биквадратичное, сепарабельное, выпуклое и другие типы программирования. Появились численные методы отыскания оптимальных решений: градиентные, штрафных и барьерных функций, возможных направлений, линейной аппроксимации, случайного поиска и др. К математическому программированию относятся также методы решения экстремальных задач с бесконечным числом переменных - бесконечномерное программирование. И, наконец, отметим, что задачи математического программирования с одной целевой функцией решаются методами скалярной оптимизации. Однако реальные ситуации настолько сложны, что нередко приходится одновременно учитывать несколько целевых функций, которые должны принимать экстремальные значения. Например, дать продукции больше, высокого качества и с минимальными затратами. Задачи, где находят решение по нескольким целевым функциям, относятся к векторной оптимизации - это так называемые задачи многокритериального подхода. Вопрос 2. Линейное программирование 2.1. Предмет линейного программирования Задачи линейного программирования образуют подмножество задач общего программирования, которое называется математическим. Отличительной особенностью задач линейного программирования является то, что цель задачи записывается с помощью линейной функции и ограничения линейные. Вычисление экстремума (максимума или минимума) линейной функции при условии, что переменные, подлежащие определению, удовлетворяют линейным ограничениям, составляет предмет линейного программирования. Линейное программирование является наиболее развитым и широко используемым на практике разделом математического программирования. Предположение о линейности экономических зависимостей несколько ограничивает возможности линейного программирования, однако простота и наглядность линейных моделей, с достаточной степенью точности описывающих экономические процессы, позволяет применять эти модели в различных видах экономической деятельности. Основы линейного программирования, как отмечалось ранее, были заложены советским математиком Л.В. Канторовичем в конце 30‑х годов. В США линейное программирование зародилось во время второй мировой войны в связи с необходимостью планирования деятельности и снабжения вооруженных сил, которые вели боевые действия в других частях света. Впоследствии эта отрасль науки получила широкое распространение в промышленности. В 1941 г. в США осуществлена постановка и простроена модель одной из центральных задач линейного программирования - транспортной задачи. Большую роль в развитии линейного программирования сыграло создание в 1947 г. американским ученым Дж. Данцигом универсального метода решения задач, который получил название "симплекс-метод". В 1949 г. Л.В. Канторовичем и М.К. Гавуриным предложен первый точный метод для решения транспортной задачи - метод потенциалов. В последующие годы вклад в развитие теории линейного программирования внесли ученые многих стран мира. Название "линейное программирование" начало применяться в 1951 г. вместо ранее использовавшегося "программирование в линейной структуре". Однако многие специалисты считали новое название неудачным и предлагали назвать эту отрасль науки "линейное планирование". Объясняли это тем, что такое название больше отвечает сущности этой отрасли науки и отличает ее от программирования на ЭВМ. Но в силу широкого распространения в мире это название было оставлено. 2.2. Построение оптимизационных моделей для решения экономических задач Процесс построения оптимизационных экономико-математиче­ских моделей условно можно разделить на следующие основные этапы. Первый этап - выбор объекта исследования. Объектом исследования могут быть различные производственно-экономические процессы: перевозка грузов, размещение производства, загрузка производственных мощностей, раскрой промышленных материалов и т.д. Второй этап - определение цели исследования. Цель исследования формулируется на основе задач, поставленных при изучении данного объекта. Например, при планировании перевозок грузов можно поставить следующую цель: составить план перевозок грузов, обеспечивающий минимальные транспортные расходы. Третий этап - выбор критерия оптимальности. Как отмечалось ранее, отличительной особенностью оптимизационных моделей является наличие условия нахождения оптимального решения (критерия оптимальности), которое записывается в виде функционала. Критериями оптимальности обычно служат: минимальная стоимость исходных материалов, минимальные издержки производства и др. К выбору критерия следует подходить очень осторожно, так как неправильно выбранный критерий может привести к решению, не отвечающему цели поставленной задачи. Четвертый этап - выявление основных ограничений. При построении моделей необходимо выявить основные ограничения задачи и включить их в модель. Реальные задачи обычно содержат большое количество ограничений. Смысл вводимых ограничений может быть различным. Практически каждая экономическая задача содержит ограничения по ресурсам, так как выбор вариантов решения производится в условиях ограниченных ресурсов (сырье, материалы, машины, оборудование, рабочая сила и др.). Кроме ограничений по ресурсам в модель включаются дополнительные условия, определяемые постановкой задачи. К ним относятся, например, обязательное соблюдение сроков выпуска продукции, ее ассортимента и качества, удовлетворение спроса на определенную продукцию и др. Ограничения в модели отражаются в виде системы уравнений и неравенств. Сформулируем две простые экономические задачи, построим математические модели для решения этих задач и покажем, что данные задачи относятся к задачам линейного программирования. Задача об использовании ресурсов. Предприятию необходимо изготавливать два вида продукции Р1, Р2 с использование трех видов ресурсов: R1, R2, R3, количество которых ограничено. Исходные данные задачи сведены в следующую таблицу: Таблица 1 Вид ресурсов Запас ресурсов Количество ресурсов, идущее на изготовление единицы продукции P1 P2 R1 36 6 6 R2 20 4 2 R3 40 4 8 Доход от реализации единицы продукции, единиц стоимости 12 15 Требуется составить такой план выпуска продукции, чтобы при ее реализации получить максимальный доход. Построение модели начнем с обозначения неизвестных. Обозначим через x1 - количество продукции P1, а через x2 - количество продукции Р2. Объектом исследования в данной задаче является планирование выпуска продукции с использованием ограниченных ресурсов. В качестве ресурсов на предприятии могут выступать оборудование, электроэнергия, топливо, различные виды сырья, рабочая сила и т.п. Единицы измерения количества продукции и ресурсов зависят от конкретного вида продукции и ресурсов, рассматриваемых в задаче (например, для готовой продукции, сырья, топлива - шт., кг, м, т, л и т.п.; для электроэнергии – кВт/ч и т.д.). Цель исследования - составление плана выпуска продукции, приносящего максимального доход. Критерий задачи - максимальный доход. Запишем формально этот критерий. Известно, что доход от реализации единицы продукции Р1 составляет 12 ед., а количество этой продукции - x1. Следовательно, доход от реализации всей продукции P1 составит 12x1 ед. Доход от реализации единицы продукции Р2 составляет 15 ед., а количество этой продукции - х2. Следовательно, доход от реализации всей продукции Р1 и Р2 должен быть максимальным, критерий задачи будет иметь вид: f=12x1+15x2  max. Известно также, что имеющиеся на предприятии ресурсы ограничены. Это обстоятельство в свою очередь необходимо отразить в модели. Предприятие производит продукцию, используя три вида ресурсов. Естественно, что фактический расход каждого вида ресурса не должен превышать запаса соответствующего вида ресурса на предприятии. Поскольку расход каждого вида ресурса на единицу каждого вида продукции и запасы ресурсов известны, это обстоятельство отражается в следующих ограничениях: 6x1+6x2 36, 4x1+2x2  20, 4x1+8x2  40. Смысл первого ограничения состоит в том, что фактический расход ресурса R1 на производство продукции Р1 и Р2 не должен превышать запаса этого ресурса на предприятии. Аналогичный смысл имеют второе и третье ограничения только для ресурсов R2 и R3 соответственно. Количество продукции, выпускаемое предприятием, должно быть величиной положительной или равной 0 (если предприятие определенный вид продукции не производит). Следовательно, в модели должны присутствовать ограничения неотрицательности переменных: x10, x20. В целом данная задача об использовании ресурсов может быть представлена моделью: f=12x1+15x2  max; x10, x20. (1) Особенность данной задачи состоит в том, что существует множество вариантов выпуска продукции Р1 и Р2, т.е. наборов значений x1 и x2, удовлетворяющих ограничениям. Однако необходимо выбрать такой вариант (или варианты) выпуска продукции, которой приносит предприятию максимальный доход. Этот вариант (или варианты) выпуска продукции будет оптимальным. Функция f и ограничения задачи линейные. Задача об использовании ресурсов относится к задачам линейного программирования и может решаться на различных предприятиях, где выпускается различное количество видов продукции с использование различного количества видов ресурсов. Учитывая это обстоятельство, сформулируем в общем виде данную задачу. Предположим, что предприятие выпускает n видов продукции с использованием m видов ограниченных ресурсов. Известны следующие величины: - запас ресурса i-го вида; - количество ресурса i-го вида, идущее на изготовление единицы продукции j-го вида; - доход от реализации единицы продукции j-го вида. Требуется составить такой план выпуска продукции, чтобы при ее реализации получить максимальный доход. Обозначим через - количество продукции j-го вида. Тогда задачу об использовании ресурсов в общем виде можно описать с помощью такой модели: (2) Задача о смесях (задача о диете). Для откорма животных необходимо из двух кормов К1 и К2 составить смесь. Задана питательность (качество) порции смеси, рассчитанной на одного животного, т.е. в ней должно содержаться: питательного вещества V1 не менее 12 ед., V2 не менее 6 ед., V3 не менее 9 ед. Другие исходные данные задачи сведены в таблицу: Таблица 2 Питательные вещества Количество питательных веществ в единице корма К1 К2 V1 3 2 V2 1 2 V3 3 1 Стоимость единицы корма, ед. стоимости 2 3 Требуется смешать имеющиеся корма в таком количестве, чтобы обеспечить заданную питательность порции смеси при минимальных затратах на корма. Построение модели начнем с обозначения неизвестных. Обозначим через x1 - количество корма К1, а через x2 - количество корма К2. Объектом изучения в данной задаче является составление смеси кормов. Единицы измерения количества смешиваемых кормов и питательных веществ (белки, жиры, углеводы и т.п.) в различных задачах могут быть разными, в частности для кормов - т, кг, л; для питательных веществ - г и т.п. Цель исследования - обеспечить заданную питательность (качество) смеси при минимальных затратах на корма. Критерий задачи - минимальные затраты. Запишем формально этот критерий. Известно, что стоимость единицы корма К1 составляет 2 ед., а количество этого корма - x1. Следовательно, стоимость всего корма К1 составит 2x1 ед. Стоимость единицы корма К2 составляет 3 ед., а количество этого корма - x2. Следовательно, стоимость всего корма К2 составляет 3x2 ед. Учитывая, что стоимость всего корма К1 и К2 должна быть минимальной, критерий задачи буде иметь следующий вид: f=2x1+3x2  min. Исходя из условия задачи, смесь должна содержать три питательных вещества, причем фактическое количество каждого питательного вещества в смеси должна быть не меньше заданного, т.е. необходимо обеспечить заданную питательность (качество) смеси. Используя заданное количество каждого питательного вещества в единице каждого корма и заданную питательность, это обстоятельство отражается в ограничениях: Смысл первого ограничения состоит в том, что фактическое содержание питательного вещества V1 в смеси должно быть не меньше заданного. Аналогичный смысл имеют второе и третье ограничения только для питательных веществ V2 и V3 соответственно. Количество корма, используемое в смеси, должно быть величиной положительной или равной 0 (если определенный вид корма в смеси не используется). Следовательно, в модели должны присутствовать ограничения неотрицательности переменных: x10, x20 В целом данная задача о смесях будет представлена моделью f=2x1+3x2  min; x10, x20. (3) Особенность данной задачи состоит в том, что существует множество вариантов смешивания кормов К1 и К2, т.е. наборов значений x1 и x2, удовлетворяющих ограничениям. Однако необходимо выбрать такой вариант (или варианты) смешивания, который обеспечивает минимальные затраты. Этот вариант (или варианты) смешивания будет оптимальным. Следовательно, данная задача, так же как и задача об использовании ресурсов, относится к задачам математического программирования, а поскольку функция f и ограничения задачи линейные, она является задачей линейного программирования. Рассмотренную частную задачу о смесях можно обобщить на случай использования n видов кормов и содержания в порции смеси m питательных веществ в количествах соответственно не менее . Известны также следующие величины: - количество i-го питательного вещества, содержащееся в единице корма j-го вида;  - стоимость единицы корма j-го вида. Требуется смешать имеющиеся корма так, чтобы обеспечить заданную питательность при минимальных затратах на корма. Обозначим через - количество корма j-го вида. Тогда задача о смесях в общем виде будет описываться моделью: (4) Замечание. Модель (4) может быть использована для решения задачи о диете человека. При решении такой задачи возможно получить нереальный для человека набор продуктов, например, 5 кг капусты, 2 кг хлеба и 1 кг огурцов. Это произойдет в силу того, что в задаче требуется обеспечить только заданную питательность при минимальных затратах на продукты. Указанные продукты вполне могут удовлетворить требованиям задачи. Естественно, что человека такой набор продуктов не может устраивать, так как ему необходимо мясо, птица, масло, картофель и др. Поэтому количество отдельных продуктов в такой задаче нужно ограничивать и в общем виде ограничение будет выглядеть так: xjdj, где dj - максимально возможное количество продукта j-го вида в диете. В компактном виде, используя знак суммирования , задачу (4) можно записать так: , , . Задачи (2) и (4) можно представить в матричной форме записи. Для этого введем следующие обозначения: C=(c1, c2, ..., cn) - матрица-строка коэффициентов при неизвестных в функции f; - матрица системы ограничений; - матрица-столбец свободных членов ограничений; - матрица-столбец неизвестных. Тогда задача (2) в матричной форме записи будет иметь вид: f=CX  max, AX  B, X  0, (5) а задача (4) запишется так: f=CX  min, AX  B, X  0. (6) Существуют задачи линейного программирования, в которых функция f максимизируется или минимизируется, а ограничения имеют вид равенств. В матричной форме записи такая задача имеет вид: f=CX  max (min), AX = B, X  0. Задачи (5), (6), (7) представляют собой частные виды задач линейного программирования. Особенность этих задач состоит в том, что они содержат только один вид ограничений. Однако наряду с этими задачами широко распространены задачи линейного программирования со смешанными ограничениями, которые содержат два или три вида рассмотренных ограничений (, , =). 2.3 Общая задача линейного программирования. Основные определения Исходя из частных видов задач линейного программирования общую задачу линейного программирования можно записать в виде следующей модели: , , , , Линейная функция f называется целевой функцией задачи. Все остальное, за исключением условий неотрицательности переменных , в дальнейшем изложении будем называть ограничениями. Любая совокупность , удовлетворяющая ограничениям, называется допустимым решением (допустимым планом) задачи. Если задача линейного программирования имеет хотя бы одно допустимое решение, то ее ограничения называются совместными, в противном случае - несовместными. Все допустимые решения образуют область применения задачи линейного программирования, или, по-другому, область допустимых решений. Допустимое решение, максимизирующее или минимизирующее целевую функцию f, называется оптимальным решением (оптимальным планом) задачи. 2.4 Графический метод решения задач линейного программирования Графическим методом можно решать, в основном, задачи линейного программирования, имеющие две переменные. В случае трех переменных графический метод становится менее наглядным, а при большом числе переменных - невозможным. Однако графический метод позволяет выявить свойства решений задачи линейного программирования, которые станут основой для рассмотрения общего метода решения задач линейного программирования. Решим графическим методом задачу линейного программирования с двумя переменными: f=x1-3x2  min (8) (9) x10, x20. (10) I этап. Графическая интерпретация области допустимых решений 1.1. Начнем решение задачи с построения области ее допустимых решений (рис. 1). В первую очередь отобразим в прямоугольной системе координат условия неотрицательности переменных (10). В двумерном пространстве уравнению соответствует прямая, а неравенству - полуплоскость, лежащая по одну сторону от прямой. Построим прямые x1=0, x2=0, которые лежат на границах полуплоскостей и совпадают с осями координат. Полуплоскости x1>0, x2>0 лежат соответственно справа от ости 0x2 и выше оси 0x1. Множество точек, удовлетворяющих одновременно неравенствам x10 и x20, представляет собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадает с точками первой четверти. 1.2. Теперь рассмотрим ограничения задачи (9). Построим по порядку прямые: 10x1+3x2=30 (I), -x1+x2=3 (II), x1-x2=4 (III), x1+x2=10 (IV). и определим, с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют соответственно строгим неравенствам: 10x1+3x2>30, -x1+x2<3, x1-x2<4, x1+x2<10. Сторона, в которой располагается полуплоскость от прямой, указывается стрелками. Убедиться в том, с какой стороны от прямой лежит полуплоскость, точки которой удовлетворяют заданному неравенству, можно путем подстановки координат точек одной или другой полуплоскости в неравенство. Когда прямая, ограничивающая полуплоскость, не проходит через начало координат, удобнее всего подставлять точку с координатами (0, 0). Если координаты точки удовлетворяют неравенству, то эта точка лежит в полуплоскости, соответствующей данному неравенству. В противном случае неравенству будет соответствовать другая полуплоскость. Рис. 1. 1.3. Область определения задачи (8)-(10) будет представлять собой пересечение всех построенных полуплоскостей. В данном случае это многоугольник АВСДЕ. Каждая точка этого многоугольника, включая и точки, лежащие на его границах, будет удовлетворять ограничениям (9)-(10). II этап. Графическая интерпретация целевой функции Следующим этапом присвоим целевой функции f значение нуль и построим прямую: f=x1-3x2=0. (11) Эта прямая, проходящая через начало координат, строится следующим образом. Легко заметить, что в левой части уравнения (11) стоит скалярное произведение двух векторов  и . Если скалярное произведение векторов равно нулю, то векторы перпендикулярны. Построим вектор  [он проходит через начало координат и точку (1, -3)] и перпендикулярно ему через начало координат проведем прямую. Это и будет прямая (11). Вектор  всегда показывает направление возрастания значения целевой функции, а противоположный ему вектор (-) - направление убывания значения целевой функции. Передвигая прямую (11) по области определения параллельно самой себе в направлении вектора , значения целевой функции будут возрастать. Передвижение в направлении вектора (-) дает убывание значения целевой функции. Передвижение на графике прямой равносильно изменению значения b в уравнении x1-3x2=b. Каждому значению b соответствует прямая. Получаемые прямые параллельны между собой и называются линиями уровня. Особенность линии уровня состоит в том, что целевая функция принимает на ней одинаковые значения, т.е. подставив координаты любой точки линии уровня в целевую функцию, ее значения изменяться не будут. Целевая функция f в задаче (8)-(10) достигает своего минимального значения в точке В многоугольника, а максимального - в точке D. III этап. Нахождение оптимального решения Оптимальному решению задачи (8)-(10) соответствует точка В, которая лежит на пересечении прямых -x1+x2=3 (II), x1+x2=10 (IV). (12) Для определения координат точки В решим систему (12). В результате получим: , ; . Перейдем теперь к рассмотрению свойств решений задачи линейного программирования. Ранее отмечалось, что все допустимые планы задачи линейного программирования образуют так называемую область определения задачи. Примем без доказательства следующую теорему: область определения задачи линейного программирования представляет собой выпуклое множество. . Рис. 2 Определение 1. Множество называется выпуклым, если ему вместе с двумя произвольными точками принадлежит и прямолинейный отрезок, их соединяющий. Например, множество планов задачи (8)-(10) является выпуклым. Если взять любые две точки, принадлежащие этому множеству, то и отрезок, соединяющий данные точки, будет также принадлежать этому множеству. Множество, изображенное на рис. 2, не является выпуклым. Определение 2. Множество называется замкнутым, если ему принадлежат все граничные точки. Замкнутое множество может быть ограниченным (рис. 3а) и неограниченным (рис. 3б, в). Множество планов задачи линейного программирования представляет собой замкнутый выпуклый многогранник (в двумерном пространстве - замкнутый выпуклый многоугольник). Вершины многогранника (многоугольника) являются его угловыми точками. Прямая, плоскость, полуплоскость, пространство, полупространство угловых точек не имеют. Теорема (без доказательства). Целевая функция задачи линейного программирования достигает своего экстремального значения в угловой точке многогранника решений. Если целевая функция принимает экстремальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, лежащей на соединяющем их отрезке. В двумерном пространстве утверждение второй части теоремы будет иметь место, если прямая f=c1x1+c2x2=0 при передвижении по области определения в необходимом направлении совпадает с одной из граничных прямых области. Такое совпадение возможно только при равенстве угловых коэффициентов данных прямых. Рис. 3а. Рис. 3б. Рис. 3в. Рис. 3г. Если целевая функция достигает своего экстремального значения в одной угловой точке, то задача имеет единственное оптимальное решение, если более чем в одной точке - то задача имеет бесконечное число оптимальных решений. Множество планов задачи линейного программирования может быть: 1) замкнутым ограниченным (рис. 3а) - в этом случае задача обязательно имеет одно или бесконечное число оптимальных решений; 2) замкнутым неограниченным (рис. 3б, в) - в этом случае задача имеет одно или бесконечное число решений, либо вообще не имеет оптимальных решений, когда в силу неограниченности множества значение целевой функции неограничено; 3) пустым (рис. 3г) - в этом случае задача допустимых решений не имеет, так как не существует точек, удовлетворяющих всем ограничениям одновременно. Кроме того, область определения задачи линейного программирования может быть представлена точкой, отрезком, лучом. Замечание. Ситуация, когда задача линейного программирования не имеет оптимального решения, возникает, как правило, в искусственно создаваемых задачах. Реальные задачи линейного программирования всегда разрешимы, т.е. должны иметь оптимальный план. Однако иногда некорректная постановка задачи может привести к ее неразрешимости. Вопрос 3. Нелинейное программирование. В большинстве инженерных задач построение математической модели не удается свести к задаче линейного программирования. Математические модели в задачах проектирования реальных объектов или технологических процессов должны отражать реальные протекающие в них физические и, как правило, нелинейные процессы. Переменные этих объектов или процессов связанны между собой физическими нелинейными законами, такими, как законы сохранения массы или энергии. Они ограничены предельными диапазонами, обеспечивающими физическую реализуемость данного объекта или процесса. В результате, большинство задач математического программирования, которые встречаются в научно-исследовательских проектах и в задачах проектирования – это задачи нелинейного программирования (НП). Пусть в математической модели проектируемого объекта или процесса непрерывная функция  представляет собой функцию цели (функцию качества), задают ограничения в виде равенств задают ограничения в виде неравенств, где  - вектор параметров проектируемого объекта, процесса или системы, оптимальные значения которых должны быть найдены. Тогда задача нелинейного программирования может быть сформулирована следующим образом: найти вектор , доставляющий минимум (максимум) целевой функции  при m линейных и (или) нелинейных ограничений в виде равенств и (p-m) линейных и (или) нелинейных ограничений в виде неравенств В течение последних двух десятилетий из нелинейного программирования выделились самостоятельные разделы: • выпуклое программирование, • квадратичное программирование, • целочисленное программирование, • стохастическое программирование, • динамическое программирование и др. Задачи выпуклого программирования – это задачи, в которых определяется минимум выпуклой функции (или максимум вогнутой), заданной на выпуклом замкнутом множестве. Эти задачи среди задач нелинейного программирования наиболее изучены. Среди задач выпуклого программирования более подробно изучены задачи квадратичного программирования. В этих задачах целевая функция – квадратична, а ограничения – линейны. В задачах целочисленного программирования неизвестные параметры могут принимать только целочисленные значения. В задачах стохастического программирования в целевой функции или в функциях ограничений содержатся случайные величины, которые подчиняются законам теории вероятностей. В задачах динамического программирования ограничения содержат как параметр время и при этом описываются дифференциальными уравнениями. Процесс нахождения решений в задачах динамического программирования является многоэтапным. Для решения задачи нелинейного программирования было предложено много методов, которые можно классифицировать по различным признакам. По количеству локальных критериев в целевой функции методы нелинейного программирования делятся на: • однокритериальные, • многокритериальные. По длине вектора  методы делятся на: • однопараметрические или одномерные (n=1), • многопараметрические или многомерные (n>1). По наличию ограничений методы нелинейного программирования делятся на: • без ограничений (безусловная оптимизация), • с ограничениями (условная оптимизация). По типу информации, используемой в алгоритме поиска экстремума методы делятся на: • методы прямого поиска, т.е. методы, в которых при поиске экстремума целевой функции используются только ее значения; • градиентные методы первого порядка, в которых при поиске экстремума функции используются значения ее первых производных; • градиентные методы второго порядка, в которых при поиске экстремума функции наряду с первыми производными используются и вторые производные. Ни один метод нелинейного программирования не является универсальным. В каждом конкретном случае необходимо приспосабливать применяемый метод к особенностям решаемой задачи. 3. Классический метод определения условного экстремума Задача нелинейного программирования (задача НП) в общем виде формулируется так: при ограничениях Где функции  нелинейны. В отличие от задачи ЛП для задач НП нет универсального метода решения. В задаче ЛП допустимое множество R всегда является выпуклым с конечным числом крайних точек. Поэтому воспользовавшись симплекс-методом и перебрав только крайние точки, можно за конечное число шагов найти оптимальное решение. В задачах НП, наоборот, выпуклость допустимого множества и конечность числа его крайних точек совсем необязательны. Это и служит причиной основной трудности решения задач НП. Для определения условного экстремума (то есть экстремума при ограничениях) можно воспользоваться методами дифференциального исчисления, когда функция  имеет не ниже второй производной. Некоторые важные понятия и теоремы классического анализа, которые лежат в основе классических методов поиска условного экстремума приведены в Приложении 1 к лекции (раздаточный материал, для самостоятельного изучения). Выводы и заключение. Из материала лекции Вы усвоили общую классификацию моделей математического программирования. Вы ознакомились с наиболее широко используемым на практике разделом математического программирования – линейным программированием. Простота и наглядность линейных моделей, с достаточной степенью точности описывающих экономические процессы, позволяет применять эти модели в различных видах экономической деятельности. Приведенная классификация методов решения задач нелинейного программирования позволит продолжить самостоятельное изучение понятий и теорем классического анализа.