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

Экономико-математические методы и модели Курс лекций рекомендован в качестве основного учебного материала студентам, получающим высшее образование в Курском институте менеджмента, экономики и бизнеса Экономико-математические типография МЭБИК. – 94с. методы и модели Идентификатор публикации: MB-МЭ-75-30-600 – Курск: Краткий курс лекций дисциплины «ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ» Составитель – Федоров Андрей Викторович, кандидат физико-математических наук, доцент Контактные данные – e-mail: [email protected] Уважаемые студенты! Курс «Экономико-математические методы и модели» направлен на формирование у обучающихся системы теоретических знаний в области экономико-математического моделирования и практических навыков использования математических методов нахождения оптимальных решений; формирование общекультурных и профессиональных компетенций в соответствии с федеральным государственным образовательным стандартом. В данном пособии кратно изложены теоретические основы и практические примеры; более полное представление о дисциплине можно получить, изучив источники из списка литературы по данному курсу, который представлен отдельным файлом. Содержание 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 1.1 Основные понятия 1.1.1. Примеры моделей, приводящих к задачам линейного программирования 1.1.2. Стандартная и каноническая формы задачи линейного программирования 1.1.3. Геометрическая интерпретация задач линейного программирования 1.2. Симплекс-метод 1.3. Двойственные задачи 1.4. Транспортная задача 2. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ 2.1. Классификация задач целочисленного линейного программирования 2.2. Метод Гомори. Метод ветвей и границ 3. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 3.1. Общая задача нелинейного программирования 3.2. Метод множителей Лагранжа 3.3. Выпуклое программирование 3.4. Квадратичное программирование 3.5. Градиентные методы 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 1.1 Основные понятия 1.1.1. Примеры моделей, приводящих к задачам линейного программирования Линейное программирование является одной из основных частей того раздела современной математики, который получил название математического программирования. В общей постановке задачи этого раздела выглядят следующим образом. Имеются какие-то переменные и функция этих переменных , которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции условии, что переменные x принадлежат некоторой области G: при В зависимости от вида функции и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что а) функция является линейной функцией переменных б) область G определяется системой линейных равенств или неравенств. Рассмотрим классический пример подобных задач. Задача о составление плана производства Рассмотрим деятельность некоторой производственной единицы (цеха, отдела и т.д.). Пусть наша производственная единица может производить некоторые товары Для производства этих товаров приходится использовать некоторые сырьевые ресурсы. Пусть число этих ресурсов есть m; обозначим их через . Tехнологией производства товара назовем набор чисел , показывающий, какое количество i-го ресурса необходимо для производства единицы товара . Это можно записать в виде технологической матрицы, которая полностью описывает технологические потребности производства и элементами которой являются числа ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... Пусть у нас имеется запасов каждого ресурса и мы планируем произвести единиц i-го товара. Так как мы не можем выйти за пределы имеющихся у нас ресурсов, то наш план производства ограничениям должен удовлетворять при очевидных условиях неотрицательности переменных : ….. Естественно, мы стремимся получить за нашу продукцию возможно больше. Поэтому стоящая перед нами задача составления плана производства приобретает вид: У нас получилась линейная целевая функция и ограничения имеют характер линейных неравенств. Таким образом, мы имеем дело с задачей линейного программирования. Задачи линейного программирования встречаются очень часто при оптимизации самых разнообразных производственных и экономических задач. 1.1.2. Стандартная и каноническая формы задачи линейного программирования Имеются стандартные формы задач линейного программирования, к которым приводят различные конкретные задачи. Прежде чем выписывать эти формы, введём обозначения. Для более краткой записи мы будем использовать векторную или матричную запись. Под векторами мы будем понимать вектора-столбцы, например , Обозначение , и т.д. будет означать, что Соответственно, запись означает, что Первая стандартная форма задачи линейного программирования имеет вид Введем вектора ; ; , a также вектора , и матрицу . Заметим, что комбинация произведение векторов есть не что иное, как скалярное и . Поэтому в векторной форме задача (1.7) примет вид Можно использовать и матричные обозначения. Тогда комбинация есть произведение и задача примет вид Вторая стандартная форма задачи линейного программирования имеет вид В векторной форме эта задача имеет вид и в матричной форме - вид Канонической формой задачи линейного программирования называется задача вида В векторной форме эта задача имеет вид и в матричной форме - вид Во всех этих задачах функцию называют целевой функцией. Вектор называют вектором коэффициентов линейной формы, вектор  вектором ограничений. Матрицу называют матрицей коэффициентов. Любой набор чисел , удовлетворяющий ограничениям задачи, называют планом, а множество всех планов  допустимой областью. Тот план, который доставляет экстремум (минимум или максимум) целевой функции, называют оптимальным планом или просто решением задачи линейного программирования. Правила приведения задач линейного программирования к стандартной и канонической формам Рассмотрим теперь те приёмы, которые позволяют произвольные формы задач линейного программирования приводить к указанным выше стандартным формам. 1. Превращение max в min и наоборот. Если целевая функция в задаче линейного программирования задана в виде , то, умножая её на (- 1), приведем её к виду , так как смена знака приводит к смене Аналогично можно заменить на на . . 2. Смена знака неравенства. Если ограничение задано в виде , то, умножая на (- 1), получим: . Аналогично, неравенство вида больше либо равно можно превратить в неравенство вида меньше либо равно . 3. Превращение равенства в систему неравенств. Если ограничение задано в виде , то его можно заменить эквивалентной системой двух неравенств , , или такой же системой неравенств со знаками больше либо равно . Указанные выше приемы позволяют приводить задачи линейного программирования к стандартной форме. 4. Превращение неравенств в равенства. Пусть исходная форма задачи линейного программирования имеет вид Здесь первые r ограничений имеют вид неравенств со знаком меньше либо равно затем идет группа неравенств со знаком больше либо равно и, наконец, группа ограничений со знаком = . Для приведения задачи к канонической форме, где все ограничения имеют вид равенств, вводят дополнительные переменные , которые тоже считаются неотрицательными и записывают исходную задачу в виде , т.е. в неравенстве со знаком меньше либо равно добавляют дополнительную неотрицательную переменную, а из неравенства со знаком больше либо равно вычитают дополнительную переменную. В целевую функцию эти дополнительные переменные включают с коэффициентом 0, т.е. фактически они в целевой функции отсутствуют. Получив решение задачи в канонической форме, для получения решения исходной задачи надо просто удалить из решения значения введенных дополнительных переменных. Пример Привести к каноническому виду задачу Введем дополнительные переменные . Переводя max в min, запишем задачу в виде что и дает эквивалентную задачу в канонической форме. 5. Ограничения на неотрицательность переменных. Во всех приведенных выше формах требуется, чтобы все переменные были неотрицательны, т.е. В реальных задачах часто на переменные накладываются ограничение вида (они называются двусторонними ограничениями), или же условие неотрицательности какой-то переменной может отсутствовать вообще. Рассмотрим, как поступать в этих случаях. а) Пусть на переменную вообще не наложено никаких ограничений. Для приведения задачи к канонической форме введем две новые переменные и и будем считать, что После этого, заменив в исходной задаче на мы получим задачу линейного программирования в канонической форме. б) Пусть на наложено двустороннее ограничение вида переменную . Тогда будет .Введем , что дает ограничения в стандартной форме. Вводя дополнительную неотрицательную переменную , можно записать двустороннее ограничение в виде После того, как в исходных соотношениях вместо выражение и добавлено ограничение, будет подставлено задача приобретет канонический вид. 1.1.3. Геометрическая интерпретация задач линейного программирования Геометрическую интерпретацию задач линейного программирования можно дать для случаев n =2 и n =3. Наиболее наглядна эта интерпретация для случая n =2, т.е. для случая двух переменных и . Пусть нам задана задача линейного программирования в стандартной форме Возьмём на плоскости декартову систему координат и каждой паре чисел поставим в соответствие точку на этой плоскости. Обратим прежде всего внимание на ограничения и . Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида рассмотрим область, соответствующую равенству . Сначала . Это прямая линия. Строить её проще всего по двум точкам. Пусть . Если взять получится , то получится . Если взять , то . Таким образом, на прямой лежат две точки и . Дальше через эти две точки можно провести прямую линию (смотри рисунок 2). Если же b=0, то на прямой лежит точка (0,0). Чтобы найти другую точку, можно взять любое отличное от нуля значение и вычислить соответствующее ему значение . Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части , а в другой наоборот . Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат (0,0). Вернёмся к задаче линейного программирования. Там имеют место m неравенств Каждое из них задает на плоскости некоторую полуплоскость. Нас интересуют те точки, которые удовлетворяют всем этим m неравенствам , т.е. точки, которые принадлежат всем Следовательно, область, геометрически изображается полуплоскостей, этим полуплоскостям определяемая определяемых общей неравенствами частью отдельными естественно, надо добавить ограничения и одновременно. вида (1.20), (пересечением) ограничениями (к всех ним, ). Как уже говорилось выше, эта область называется допустимой областью задачи линейного программирования. Пример Найти допустимую область задачи линейного программирования, определяемую ограничениями Решение Рассмотрим прямую . При , а при . Таким образом, эта прямая проходит через точки (0,1) и (-1,0). Взяв получим, что -0+0<1 и поэтому интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4а. Рассмотрим прямую . При , а при . Таким образом, эта прямая проходит через точки (0, -1/2) и (1,0). Так как , то интересующая нас полуплоскость лежит выше прямой, изображенной на рис. 4.б. Наконец, рассмотрим прямую . Она проходит через точки (0,3) и (3,0) и так как 0+0<3, то интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4.в. Сводя все вместе и добавляя условия получим рисунок 5, где выделена область, в которой выполняются одновременно все ограничения. Получившаяся область имеет вид выпуклого многоугольника. Вернемся теперь к общему случаю, когда одновременно выполняются неравенства Не приводя строгих доказательств, укажем те случаи, которые тут могут получится. Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника ( см. рис. 6). Неосновной случай - получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 7. Подобная ситуация, например, получится, если в рассмотренном выше примере убрать ограничение . Оставшаяся часть будет неограниченным выпуклым многоугольником. Наконец, возможен случай, когда неравенства противоречат друг другу, и допустимая область вообще пуста. Вернёмся к исходной задаче линейного программирования. В ней, кроме системы неравенств, есть еще целевая функция . Рассмотрим линию уровня целевой функции – прямую . Что будет происходить с прямой при увеличении L? прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором , так как это  вектор нормали к нашей прямой и одновременно вектор градиента функции . А теперь сведем всё вместе. Итак, надо решить задачу Oграничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L прямая пересекает допустимую область. Это пересечение дает какие-то значения переменных , которые являются планами. Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 9). В конце концов эта прямая выйдет на границу допустимой области  как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение прямой с допустимой областью будет пустым. Поэтому, то положение прямой граничную точку допустимой , при котором она вышла на области, и даст решение задачи, а соответствующее значение L и будет оптимальным значением целевой функции. Пример Решить задачу Решение Допустимая область изображена на рис. 5. Повторим еще раз этот рисунок, оставив только допустимую область и нарисовав дополнительно прямые (см. рис. 10). Пусть, например, L=2. Тогда прямая проходит через точки (2,0) и (0,1) и изображена на рис. 10. Будем теперь увеличивать L. Тогда прямая начнёт двигаться параллельно самой себе в направлении, указанном стрелкой. Максимальное значение L получится тогда, когда прямая пройдет через вершину многоугольника, указанную на рисунке, и дальнейшее увеличение L приведет к тому, что прямая выйдет за пределы многоугольника и её пересечение с допустимой областью будет пустым. Выделенная вершина лежит на пересечении прямых и поэтому имеет координаты . Это и есть решение нашей задачи, т.е. есть оптимальный план задачи. При этом значение целевой функции Оптимальный , что и дает её максимальное значение. план, как правило, соответствует какой-то вершине многоугольника, изображающего допустимую область. И лишь в том случае, когда прямая параллельна граничному отрезку допустимой области, решение не будет единственным (рис. 11). Но и в этом случае вершины, соответствующие границам этой стороны, дают оптимальные планы нашей задачи линейного программирования. Ну, а если допустимая область неограничена, то и значение целевой функции может быть неограниченным. Таким образом, можно сформулировать следующие положения: 1. допустимая область – это выпуклый многоугольник; 2. оптимум достигается в вершине допустимой области (если допустимая область ограничена и не пуста); 3. ограниченность целевой функции в допустимой области является необходимым и достаточным условием разрешимости задачи. 1.2. Симплекс-метод 1.2.1. Выпуклые множества и многогранники к более строгому изложению основ теории линейного программирования, хотя будут изложены лишь наиболее простые результаты. Перейдем теперь Рассмотрим n-мерное евклидово пространство пространстве. Рассмотрим две точки . Множество точек и пусть  точка в этом и , принадлежащие , которые могут быть представлены в виде (в координатах это записывается так: выпуклой комбинацией точек и , называется , или отрезком, соединяющим точки и . Сами точки и называются концами отрезка. В случаях n =2 и n =3 это  отрезок в обычном понимании этого слова на плоскости или в пространстве (см. рис. 12). Заметим, что при  =0 , а при  =1 Пусть в , т.е. при  =0 и  =1 получаются концы отрезка. заданы k точек . Точка называется выпуклой комбинацией точек . Пусть есть некоторая область в пространстве множество точек из ). , где все и (другими словами, G есть некоторое Определение. Множество (область) называется выпуклым, если из того, что и следует, что для   [0,1]. Другими словами, G  выпуклое множество, если оно, вместе с любыми двумя своими точками, содержит в себе отрезок, соединяющий эти точки. На этих рисунках "а" и "б" - выпуклые множества, а "в" не является выпуклым множеством, так как в нём есть такая пара точек, что соединяющий их отрезок не весь принадлежит этому множеству. Теорема 1. Пусть G  выпуклое множество. Тогда любая выпуклая комбинация точек, принадлежащих этому множеству, также принадлежит этому множеству. Теорема 2. Допустимая область задачи линейного программирования является выпуклым множеством. По аналогии с двумерным или трехмерным случаями, при любом n эту область называют выпуклым многогранником в n - мерном пространстве . Теорема 3. Множество оптимальных планов задачи линейного программирования выпукло (если оно не пусто). Теорема 4. Для того, чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы целевая функция на допустимом множестве была ограничена сверху (при решении задачи на максимум) или снизу (при решении задачи на минимум). 1.2.2. Вершины выпуклого многогранника На примере задачи линейного программирования с n=2 мы видели, что особую роль играют вершины допустимой области. Но что понимать под вершиной выпуклого многогранника при n>3, когда не существует геометрически наглядного образа? Легко заметить, что при n=2 и n=3 вершина выпуклого многогранника  это такая точка, которая не является внутренней точкой никакого отрезка, концы которого принадлежат этому многограннику (рис 14). Этим свойством обладают только вершины. Определение. Вершиной или крайней точкой выпуклого многогранника называется любая его точка, которая не является внутренней точкой никакого отрезка, целиком принадлежащего этому многограннику. Сформулируем несколько важных теорем, касающихся вершин выпуклых многогранников. Теорема 1. Любая точка выпуклого многогранника является выпуклой комбинацией его вершин. Теорема 2. (Основная теорема линейного программирования) Целевая функция задачи линейного программирования достигает своего экстремума (минимума или максимума) в вершине допустимой области. Если целевая функция достигает экстремального значения более, чем на одной вершине, то она достигает того же значения в любой точке, являющейся выпуклой комбинацией этих вершин. Эта теорема имеет важнейшее значение, так как она указывает путь решения задачи линейного программирования. Совсем не надо перебирать все точки допустимой области. Достаточно перебрать вершины допустимой области, а ведь их - конечное число. Кроме того, как это окажется далее, не нужно перебирать все вершины, можно этот перебор существенно сократить. Только вот как узнать, имеем ли мы дело с вершиной или нет? Все дальнейшее изложение будет вестись для задач линейного программирования в канонической форме в векторных обозначениях. Теорема 3. Если известно, что система векторов независима и такова, что где все линейно , то точка является вершиной допустимой области. Замечание. Заметим, что в отличны от нуля совсем не обязательно первые k компонент. Первыми мы написали их только для упрощения доказательства, а вообще речь идет о любых k компонентах из общего числа n компонент. Теорема 4. Если вершина, то вектора отличным от нуля компонентам , соответствующие , образуют линейно независимую систему. Пусть число ограничений в задаче линейного программирования равно m .Так как каждая система из векторов в m-мерном пространстве линейно зависима, то среди компонент плана, соответствующего вершине, не более m отличных от нуля компонент. Определение. План, соответствующий вершине допустимой области, называется опорным планом. Если опорный план имеет ровно m отличных от нуля компонент, то он называется невырожденным опорным планом. Если число ненулевых компонент опорного плана меньше m, то он называется вырожденным опорным планом. Проблема вырожденных опорных планов - сложная проблема. В обычных ситуациях вырожденные опорные планы встречаются очень редко. Поэтому в этой главе мы всюду далее будем считать, что все опорные планы невырождены. 1.2.3. Переход от вершины к вершине Раз экстремум целевой функции достигается на одной из вершин многогранника допустимой области, то нет необходимости исследовать все точки области. Надо лишь "пройтись" по вершинам многогранника. Но для этого нужно уметь переходить от одной вершины к другой. Пусть нам известен какой-то опорный план (вершина), соответствующий m векторам из первоначальной системы n векторов. Будем считать, что этими векторами являются первые m векторов из системы векторов , где все Так как векторы верно разложение (координаты вектора . Для него . линейно независимы, то они образуют базис в m -мерном пространстве и любой из векторов любого Опорный план имеет вид в базисе может быть разложен по этому базису, то есть для , где  коэффициенты разложения по базису . Возьмем какой-то вектор, не входящий в наш базис, скажем, вектор . Для него Пусть хотя бы один из коэффициентов положителен. Возьмем некоторую величину , умножим на неё обе части равенства (5) и вычтем из (3). Тогда получим Вектор в случае неотрицательности всех своих компонент является планом. Те компоненты, где , будут автоматически неотрицательны. Чтобы остальные компоненты были неотрицательны, надо, чтобы Отсюда имеем: Возьмем , где минимум берется по всем тем индексам i , для которых , то все компоненты плана будут неотрицательны. Но давайте возьмем  в точности равным i =1, то есть . Очевидно, что если . Пусть, например, . Но тогда компонента достигается при обратится в ноль и мы получим план , где , который опять содержит ровно m отличных от нуля положительных компонент. Докажем, что это - новая вершина, то есть это  новый опорный план. Действительно, этому новому плану соответствуют векторы то есть существуют такие числа . Допустим, что они линейно зависимы, , не все равные нулю, что векторы уже были линейно независимы, поэтому тогда ,где . Но . Но раньше у нас было . Так как разложение по базису определяется однозначно, то должно быть частности, должно быть =0. Это противоречит тому, что , в >0. Значит, система векторов линейно независима и мы перешли к новой вершине, то есть получили новый опорный план. Отметим следующее. Если все , то мы не в состоянии проделать эту процедуру. Зато, неограниченно увеличивая , мы можем получить план со сколь угодно большими компонентами. Значит, в этом случае допустимая область неограничена. 1.2.4. Переход к новому базису В старом базисе этому базису мы имели следующие разложения векторов по (8) Теперь мы перешли в новую вершину, которой соответствует базис и, чтобы иметь возможность двигаться дальше к следующей вершине, мы должны иметь разложения векторов есть Выведем формулы для туда вектор по этому новому базису, то . Мы должны вывести из базиса вектор . Поэтому возьмём выражение для вектора , выразим из него вектор и подставим это выражение в (8). Тогда мы получим Перегруппировывая слагаемые, получим: Таким образом, координаты вектора в новом базисе имеют вид и ввести что и дает разложение векторов по новому базису. 1.2.5. Отыскание оптимального плана Пусть мы стремимся к минимуму целевой функции, то есть нашей задачей является Очевидно, что довольно трудоемко перебирать все вершины многогранника, соответствующего допустимой области. Лучше идти по вершинам так, чтобы при переходе от вершины к вершине значение целевой функции уменьшалось. Именно в этом и состоит идея метода решения задачи линейного программирования, которая получила название симплекс-метода. Итак, основная идея симплекс-метода заключается в том, чтобы так переходить от вершины к вершине, чтобы при каждом переходе значение целевой функции уменьшалось или увеличивалось. Именно так из любой вершины можно добраться до оптимальной вершины и получить оптимальный план. Пусть известен опорный план линейно независимых векторов где все , и связанная с ним система . Тогда имеем - коэффициенты целевой функции и  её значение, соответствующее данному опорному плану. Поскольку векторы линейно независимы, любой вектор системы можно разложить по этим векторам: Введем величины функции, стоящий при , где - коэффициент целевой (то есть соответствующий вектору ). Теорема 1.9. Если для некоторого j выполняется условие , то можно уменьшить значение целевой функции, причем: Случай 1. Если целевая функция ограничена снизу, то можно построить опорный план с меньшим значением целевой функции, чем предыдущий; Случай 2. Если целевая функция неограничена снизу, то можно построить план, соответствующий сколь угодно малому значению целевой функции. Теорема 1.10. Если для некоторого опорного плана для всех j справедливы неравенства , то он является оптимальным. Эта теорема дает критерий оптимальности опорного плана. Теоремы 1.9 и 1.10 дают возможность, начав с некоторого исходного опорного плана, получать последовательность все более лучших опорных планов, которые завершатся либо оптимальным планом, либо будет показано, что целевая функция неограничена. Отметим следующее: 1. Если при вычислении минимум достигается при нескольких i, то для вывода из базиса обычно берут вектор 2. Для определения вектора , для которого разность с наименьшим индексом. , вводимого в базис, обычно берут тот вектор наибольшая. 1.2.6. Алгоритм симплекс-метода Сформулируем алгоритм симплекс-метода для решения задач линейного программирования, заданных в канонической форме. Обычно он реализуется в виде так называемой симплекс-таблицы, изображенной на следующей странице. В первом столбце этой таблицы располагаются обозначения векторов, входящих в базис. Второй столбец  коэффициенты векторам, входящим в базис. целевой функции, соответствующие Третий столбец  компоненты опорного плана. В дополнительной строке в этом столбце пишется величина . Её легко вычислить, перемножая числа из второго столбца и третьего столбца и складывая их. Далее идут столбцы, соответствующие всем векторам , и в этих столбцах записываются координаты этих векторов в рассматриваемом базисе. Заметим, что для векторов, входящих в базис, эти координаты имеют вид (0,0, ... ,0,1,0, ..., 0), где единица стоит в той строке, где находится сам этот базисный вектор. В дополнительной строке сверху обычно выписывают коэффициенты , соответствующие этим векторам. В дополнительной строке снизу пишутся величины , вычисляемые по формулам: . Заметим, что для векторов, входящих в базис, эти разности всегда равны нулю. Далее идут следующие этапы, связанные с преобразованием этой таблицы. При ручном счете каждый раз эту таблицу лучше переписывать заново, при счете на ЭВМ (используется при решении практических, а не учебных задач), эта таблица просто преобразуется в памяти ЭВМ. Этап 1 Просматривается дополнительная строка снизу, где записаны разности . Если все эти разности , то план является оптимальным Этап 2 Если есть столбцы, где , то выбирается столбец с максимальным значением этой разности. Индекс j определит вектор, вводимый в базис. Пусть , то есть в базис надо вводить вектор . Назовем столбец, соответствующий этому вектору, направляющим столбцом. В дальнейшем мы будем направляющий столбец помечать символом . Этап 3 Просматривается столбец, соответствующий этому вектору. Если все значения целевой функции неограничены снизу. Если есть где просматриваются лишь те дроби , то , то находятся , для которых Пусть этот минимум достигается для вектора . Тогда именно вектор подлежит выводу из базиса. Строка, соответствующая этому вектору, называется направляющей строкой. В дальнейшем в примерах мы будем помечать ее символом . Этап 4 После того, как определены направляющие столбец и строка, начинает заполняться новая симплекс-таблица, в которой на месте направляющей строки будет стоять вектор . Обычно заполнение этой новой таблицы начинается именно с направляющей строки. В качестве компоненты опорного плана туда пишется величина , то есть . Остальные элементы этой строки заполняются величинами Обратите внимание на особую роль элемента . , стоящего на пересечении направляющей строки и направляющего столбца. Именно на него делятся все бывшие элементы направляющей строки. На месте бывшего элемента автоматически появляется единица. Написанные выше формулы для пересчета элементов направляющей строки можно записать следующим правилом: . Этап 5 Далее начинается пересчет всех остальных строк таблицы, включая и дополнительную нижнюю строку по формулам: для компонент плана ; для координат разложения по базису ; для дополнительной строки . Обратите внимание на то, что все эти формулы по сути дела строятся по одному правилу . Это правило применимо и к компонентам плана, и к величинам , и к разностям . Его даже можно использовать для пересчета элементов самого направляющего столбца, хотя проще заполнить его нулями, оставив 1 на месте бывшего элемента . Далее итерации продолжаются. Пример Решить задачу линейного программирования В данном случае вектор равен (0,1,-3,0,2,0), а в векторной форме ограничения могут быть записаны в виде . Заполним исходную симплекс-таблицу, взяв в качестве исходного базиса вектора , что удобно из-за их вида. Исходная симплекс-таблица Ба- План 0 1 -3 0 2 -1 0 2 1 зис 0 7 1 3 0 12 0 10 0 -2 4 0 -4 3 1 8 0 -1 3 -2 0 Обратите внимание на то, что из-за специфического вида векторов "план" просто переписался вектор в столбец , а в качестве координат векторов в нашем базисе стоят просто сами векторы. Ну, а величины приходится считать: Первая итерация Просматривая дополнительную строку мы видим, что в ней всего один положительный элемент  в столбце, соответствующем вектору . Следовательно, этот вектор надо вводить в базис и этот столбец и будет направляющим столбцом. В этом направляющем столбце есть два положительных числа  4 и 3. Поэтому нужно рассмотреть два частных и выбрать из них наименьшее. Так как и он достигается на векторе , то этот вектор подлежит выводу из базиса и соответствующая ему строка и будет направляющей строкой. Базис План 0 1 -3 2 10 1 2 -3 3 1 1 8 1 -9 -2 Заполним теперь новую симплекс-таблицу, следуя сформулированным выше правилам. Начинается заполнение, естественно, со второй строки (так как она была направляющей), а затем пересчитываются все остальные строки. Вторая итерация Просматривая дополнительную строку мы вновь видим в ней всего один положительный элемент это 1/2, стоящая в столбце вектора . Следовательно, этот вектор надо ввести в базис и этот столбец будет направляющим. В столбце, соответствующем вектору , всего один положительный элемент это 5/2, которая стоит в первой строке. Поэтому первая строка будет направляющей и вектор должен быть выведен из базиса. Ба- План 0 1 -3 2 4 1 -3 5 1 зис 1 1 -11 10 1 Запишем новую симплекс-таблицу, следуя сформулированным выше правилам. В получившейся таблице в дополнительной строке стоят лишь отрицательные числа и нули. Поэтому получившийся план является оптимальным. Итак, оптимальный план имеет вид , то есть , а все остальные Ему соответствует значение целевой функции, равное -11. 1.2.7. Метод искусственного базиса Последняя трудность, которую осталось преодолеть  это определение исходного опорного плана и исходной симплекс-таблицы, с которой начинаются все итерации. За счет чего мы так легко составили исходную симплекс-таблицу в предыдущем примере? Легко видеть, что это произошло потому, что среди векторов были векторы вида , так как искать координаты в этом базисе очень просто. На искусственном введении этих векторов и основан метод искусственного базиса. Итак, пусть мы имеем задачу линейного программирования в канонической форме . Можно считать, что все , так как умножением соответствующего ограничения на -1 у всегда можно сменить знак. Возьмем очень большое число M и будем решать следующую вспомогательную задачу: В этой задаче сразу ясен исходный базис  в качестве него надо взять векторы, стоящие при , ведь они имеют вид В качестве исходного опорного плана надо взять план Коэффициенты разложения векторов . Исходная симплекс-таблица приобретает тогда вид: Надо лишь сосчитать дополнительную строку, где стоят числа : и Заметим, что в матричных обозначениях исходная симплекс-таблица выглядит так: , где - единичная матрица размерности ,а . А теперь начнем преобразования симплекс-таблицы, стараясь выводить из базиса векторы, соответствующие введенным дополнительным переменным. Так как M очень большое, то среди разностей будет много положительных и будет много претендентов на введение в базис из векторов . Заметим, что если какой-то вектор, соответствующий какой-то дополнительной переменной выведен из базиса, то соответствующий столбец симплекс- таблицы можно просто вычеркнуть и больше к нему не возвращаться. В конце концов возможны два варианта. Вариант 1 Все векторы, соответствующие введенным дополнительным переменным, будут выведены из базиса. В этом случае мы просто вернемся к исходной задаче, попав в какую-то вершину допустимой области. Все столбцы симплекстаблицы, соответствующие дополнительным переменным, тогда исчезнут и дальше будет решаться исходная задача. Вариант 2 Несмотря на то, что M очень велико, получающийся оптимальный план будет все-таки содержать какую-то из дополнительных перем енных. Это означает, что допустимая область исходной задачи пуста, то есть ограничения исходной задачи противоречивы и поэтому исходная задача вообще не имеет решений. Заметим в заключение, что величина M вообще не конкретизируется и так и остается в виде буквы M. При решении учебных задач в дополнительную строку пишут алгебраические выражения, содержащие M, а при счете на ЭВМ вводится еще одна дополнительная строка, куда пишутся коэффициенты при M. Пример Решить задачу линейного программирования Заметим, что у нас уже есть один подходящий вектор  это вектор переменной . Поэтому вводим лишь две дополнительные переменные исходную задачу следующей: при , заменяя Исходная симплекс-таблица примет тогда вид: Ба- с План -1 -2 -3 1 М М зис M 15 1 2 3 1 M 20 2 1 5 1 1 10 1 2 1 1 10+ 2+ 4+ 4+ 35M 3M 3M 8M Первая итерация Так как из базиса выводится вектор , то в получающейся симплекс-таблице соответствующий столбец сразу удаляется. Ба- с Пла -1 -2 -3 1 М M 3 1 -3 4 1 1 1 н зис 6 -6+ 2/5- 16/5+ 3M - +1/5 1/5 M M Вторая итерация На этой итерации из базиса выводится вектор . Соответственно из симплекс- таблицы удаляется столбец, соответствующий этому вектору, и все введенные дополнительные переменные исчезают. Ба- с План -1 -2 -3 1 -2 1 -3 1 1 1 зис Третья итерация Мы вернулись к исходной задаче и продолжаем решать ее по стандартной схеме. Ба- с План -1 -2 -3 1 зис -2 1 -3 1 -1 1 -15 -1 Таким образом, задача решилась и оптимальный план имеет вид: . Минимальное значение целевой функции равно –15. Отметим в заключение, что если первоначальная задача линейного программирования имела ограничения вида и все компоненты вектора неотрицательны, то, приводя её к канонической форме, мы сразу будем иметь единичную матрицу порядка m которую и можно брать в качестве исходного базиса. 1.3. ДВОЙСТВЕННЫЕ ЗАДАЧИ 1.3.1. Постановка двойственных задач Симметричные двойственные задачи Рассмотрим задачу линейного программирования в стандартной форме (1) или в матричной форме (2) Рассмотрим теперь следующую задачу (3) или в матричной форме (4) Пара задач (1) и (3) (или, в матричной форме, пара задач (2) и (4) ) называются двойственными друг другу задачами в симметричной форме. Несимметричная двойственная задача Исходная задача имеет вид: (5) или, в матричной форме (6) Двойственная задача в несимметричной форме имеет вид (7) или в матричной форме (8) Отметим, что в несимметричной двойственной задаче не накладывается условие неотрицательности переменных. Если исходная задача линейного программирования записана в произвольной форме, то для записи двойственной задачи следует сначала записать исходную задачу в канонической или стандартной форме, а затем выписать двойственную задачу. При желании, получившуюся двойственную задачу также можно привести к какой-либо нестандартной форме. Экономическая интерпретация двойственной задачи в симметричной форме Исходная задача: Обычно эта задача связывается с задачей максимизации дохода при производстве некоторой продукции при наличии ограничений на ресурсы. Коэффициенты имеют смысл дохода от единицы продукции j-го ресурса, — количество единиц продукции j-го вида. Коэффициенты имеют смысл затрат i-го ресурса на производство продукции j-го типа. Что же представляет двойственная задача по своему смыслу? Целевая функция двойственной задачи: , а ограничения: , где (1) — затраты i-го ресурса на производство единицы продукции j-го типа, а (2) — доход от продажи единицы продукта i-го типа. Поэтому в целевой функции на месте (?)получаем смысл стоимости всех ресурсов, т. е. Задача приобретает смысл: ограничениях: , при , где  (3) — запасы i-го ресурса;  (4) — стоимость единицы i-го ресурса;  (5) — общая стоимость всех ресурсов;  (6) — запасы i-го ресурса на производство единицы продукции j-го типа;  (7) — цена единицы i-го ресурса;  (8) — доход от продажи единицы продукции i-го вида. Таким образом, задачи симметричной двойственной пары могут быть сформулированы так. 1. Исходная задача. Сколько единиц выпустить при доходе продукции каждого вида надо от продукции единицы j-го типа при имеющихся запасах каждого из ресурсов , чтобы получить максимальный доход? 2. Двойственная задача. Какую цену следует назначить единице каждого из ресурсов , чтобы при заданных величинах дохода от производства единицы каждого вида продукции минимизировать стоимость затрат? Переменные называется по-разному. Часто их называют учетными, неявными или фиктивными ценами. 1.3.2. Свойства двойственных задач Сформулируем несколько теорем. Теорема 1. Для пары (как симметричной, двойственных задач верно соотношение так и несимметричной) . Следствие 1. Если в одной задаче из пары двойственных задач целевая функция неограничена, то во второй задаче допустимая область пуста. Следствие 2. Если для планов и исходной и двойственной задач выполняется соотношение , то они являются оптимальными планами соответствующих задач. Теорема 2. Для пары двойственных задач имеет место соотношение . Теорема 3. ( В формулировке для несимметричной двойственной задачи) Если i-ая компонента оптимального плана исходной задачи строго положительна, то i-ое ограничение двойственной задачи при подстановке в нее оптимального плана превращается в строгое равенство . Если i-ая компонента оптимального плана исходной задачи равна нулю, то i-ое ограничение двойственной задачи при подстановке в нее оптимального плана имеет вид . Теорема 3. (В формулировке для симметричной двойственной задачи). Если i-ая компонента оптимального плана какой-то задачи положительна, то i-ое ограничение двойственной ей задачи, при подстановке в не оптимального плана, превращается в строгое равенство. Наоборот, если i-ое ограничение какой-то задачи, при подстановке в него оптимального плана, превращается в строгое неравенство, то i-ая компонента оптимального плана двойственной ей задачи равна нулю. На основе теории двойственности основан ряд методов решения задач линейного программирования. В частности, на ее базе строится метод решения рассматриваемой ниже транспортной задачи. 1.3.3. Двойственный симплекс-метод Это название закрепилось за методом последовательного улучшения, применяемым к задаче, записанной в виде: Определение 1.5. Решение системы линейных уравнений, определяемое базисом, называется псевдопланом задачи, если для любого j. Двойственный симплекс-метод позволяет за конечное число итераций найти оптимальный план двойственно невырожденной задачи, или обнаружить, что множество планов пусто. Теорема 1.14. Если в псевдоплане, определяемом базисом из mвекторов, есть хотя бы одно отрицательное число, для которого все координаты вектора больше либо равны 0. Теорема 1.15. Если в псевдоплане, определяемом базисом из m векторов, есть хотя бы одно отрицательное число, для которого хотя бы одна координата вектора меньше 0, то можно перейти к новому псевдоплану, при котором значение целевой функции уменьшится. Теорема 1.16. При решении задачи двойственным симплекс-методом одновременно строится и оптимальный план другой (двойственной) задачи или устанавливается неограниченность снизу. Алгоритм двойственного симплекс-метода Этап 1. Находим псевдоплан задачи. Этап 2. Проверяем псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану. Этап 3. Выбираем направляющую строку с помощью определения наибольшего по абсолютной величине компоненты плана и направляющий столбец находят при подсчете наименьшей по абсолютной величине отношения элементов строки разностей к соответствующим отрицательным элементам направляющей строки. Этап 4. Находим новый псевдоплан и продолжают действия с этапа 2. Пример № 1. Рассмотрим задачу Решение: Запишем эту задачу в канонической форме: Умножив первое и второе уравнения системы ограничений этой задачи на -1, перейдем к задаче вида: Построим для этой задачи двойственную: Выберем в качестве базиса векторы , . 19 21 0 -20 -2 -5 1 -20 -4 -1 1 -19 -21 0 Находим величину строку направляющей. . Можно выбрать первую или вторую Тогда по величине направляющим столбцом будет столбец . План: Координаты: ; ; ; . В результате: 21 4 19 21 0 2/5 1 -1/5 -1/5 1 -16 -18/5 42/5 21 -21/5 0 84 -137/5 0 -21/5 0 . Находим величину . Направляющая строка - вторая. Тогда по величине . направляющим столбцом будет столбец . План: Координаты: ; ; ; 19 21 0 21 20/9 0 1 -2/9 1/9 19 40/9 1 1/18 -5/18 19 21 65/18 53/18 84 65/18 53/18 В результате получили оптимальный план . 1.4. ТРАНСПОРТНАЯ ЗАДАЧА 1.4.1. Постановка задачи Имеется целый набор специфических, для которых разработаны особые методы решения, задач линейного программирования . В качестве примера таких задач мы рассмотрим так называемую транспортную задачу. Начнем с её содержательной формулировки. Пусть имеется некоторый однородный продукт, сосредоточенный на m пунктах отправления (складах), так что на i-м складе находится единиц этого продукта. Этот продукт необходимо доставить в n пунктов назначения (потребления), причем на j-й пункт необходимо доставить единиц продукта. Запасы и потребности сбалансированы, то есть , то есть наличие продукта равно потребности в нем. Пусть стоимость перевозки единицы продукта из i-го склада в j-й пункт назначения равна . Пусть есть то количество продукта, которое перевозится из i-го склада в j-й пункт потребления. Тогда общие транспортные расходы составят величину . Из каждого склада весь продукт должен быть вывезен. Это значит, что должно быть выполнено условие . С другой стороны, потребности j-го пункта назначения должны быть полностью удовлетворены. Это означает, что . Желание минимизировать транспортные расходы приводит нас к следующей задаче: являющейся типичной задачей линейного программирования. Определение 3.1. Транспортная задача называется открытой транспортной задачей, если условие баланса нарушаются; в случае выполнения условия баланса она называется сбалансированной транспортной задачей. Однако у этой задачи есть одна очень существенная особенность: в ограничениях перед неизвестными всегда стоит 1. И именно это позволяет разработать гораздо более эффективные и простые алгоритмы решения транспортной задачи, чем симплекс-метод. Приведение открытой транспортной задачи к сбалансированной 1. Превышение запасов над потребностями. В этом случае вводится “фиктивный” потребитель с потребностями равными абсолютной величине разности между общим количеством запасов и общим количеством требуемых единиц. Стоимость по доставке будет для потребителя равна 0, т.к. поставки фактически нет. 2. Превышение потребностей над запасами. Вводим “фиктивного” производителя (склад) с потребностями равными абсолютной величине разности между общим количеством запасов и общим количеством требуемых единиц. Стоимость по доставке будет для производителя равна 0, т.к. поставки фактически нет. 1.4.2. Простейшие свойства транспортной задачи Теорема 1. Для любой транспортной задачи существует план (то есть для любой транспортной задачи допустимая область не пуста). Теорема 2. Транспортная задача всегда имеет оптимальный план. Теорема 3. Любой опорный план имеет не более положительных компонент. Следствие. Оптимальный план содержит не более, чем 1.4.3. Методы определения первоначального опорного плана перевозку. Метод северо-западного угла Для начала решения транспортной задачи необходимо иметь какой-то исходный опорный план, то есть оказаться в какой-то вершине допустимой области. Приведем конструктивный прием построения такого опорного плана, получивший название "метод северо-западного угла". и n пунктов потребления с Итак, пусть имеется m складов с запасами потребностями . Пусть запасы и потребности сбалансированы, то есть . Представим это в виде таблицы ... где в столбце справа указаны запасы, в строке снизу  потребности, а пустые клетки оставлены для будущего плана перевозок. Начнем заполнение с клетки, расположенной вверху слева, то есть с "северозападного угла". Вместо впишем число . Возможны два варианта. 1. , то есть . Тогда, запланировав перевозку из первого склада в первый пункт потребления в объеме мы полностью опустошим первый склад и там ничего не останется. Поэтому все остальные перевозки из первого склада могут быть только нулевые. Ну, а потребность в первом пункте потребления останется в объеме . Наша таблица примет вид: ... 0 ... Отметим, что оставшаяся незаполненной часть таблицы вновь по структуре та же, что и исходная таблица, только в ней на одну строку меньше. 2. , то есть пункт потребления в объеме . Тогда, запланировав перевозку из первого склада в первый , мы полностью удовлетворим его потребности. Перевозить туда больше будет ничего не надо, поэтому остальные перевозки туда будут равны нулю. В первом складе еще останется запасов продукта. Наша таблица примет вид: ... Отметим, что оставшаяся незаполненной часть таблицы вновь по структуре та же, что и исходная таблица, только в ней на один столбец меньше. Ну, а дальше все можно повторить, продолжая заполнять оставшуюся часть таблицы перевозок начиная с левого верхнего, "северо-западного" угла, пока не будут исчерпаны запасы всех складов и не удовлетворены потребности всех пунктов потребления. У нас всего в таблице m строк и n столбцов. Каждый раз исчезает, как минимум, либо строка, либо столбец (могут исчезнуть сразу и строка, и столбец, если запасы какого-то подмножества складов полностью удовлетворят потребности какого-то подмножества пунктов потребления). Однако при последней перевозке исчезает сразу и последняя строка, и последний столбец. Поэтому получающийся план перевозок содержит не более компонент. Мы не будем доказывать, что план, полученный методом северо-западного угла, является опорным. Заметим лишь, что если получающийся план содержит ровно компоненту, то он называется невырожденным. Если число положительных компонент плана перевозок меньше , то он называется вырожденным. Рассмотрим два примера. С целью экономии места, вся таблица не переписывается, а лишь приписываются последние строки и столбцы. Пример Пусть 3 3 6 3 4 4 8 8 8 4 3 6 9 9 9 9 9 6 3 7 7 6 В данном случае число 7 7 6 складов m =3, число пунктов 4 7 6 потребления n =4, так что 7 6 m+n-1=6. Получившийся 3 6 опорный план содержит ровно 6 6 компонент, и поэтому являет0 ся невырожденным. Пример Пусть Аналогичная процедура приводит к таблице, изображенной ниже. В этом случае получившийся опорный план имеет всего 5 компонент, то есть является вырожденным. Это 3 3 6 3 4 4 4 4 7 6 13 13 13 13 6 3 7 7 6 В данном случае число скла- 7 7 6 дов m =3, число пунктов потре- 4 7 6 бления n =4, так что m+n-1=6. 7 6 Получившийся опорный план 6 содержит 5 компонент, и поэтому является вырожденным. произошло потому, что запасы складов потребности пунктов потребления сбалансированные потребности обнулились сразу и строка, и столбец. и и полностью удовлетворили и поэтому в тот момент, когда эти удовлетворились ( ), Ниже вся теория будет строится для случая, когда все опорные планы невырожденные, то есть все они имеют компоненту. Как бороться с явлением вырождения, которое в транспортных задачах встречается достаточно часто - будет рассказано в самом конце. Метод минимального (максимального) элемента Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел и . Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Пример Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида: 2 3 4 15 11 6 10 1 8 9 3 3 4 1 2 21 10 20 10 Решение: Задача сбалансирована. Строим первоначальный опорный план методом минимального элемента. 1. Выясним минимальную стоимость перевозок. перевозка будет осуществляться с пункта производства Первая в пункт потребления и она составит максимально возможное число единиц продукта :. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки .Выясним минимальную стоимость перевозок (без учета столбца № 2). 2. Вторая и третья перевозки будут осуществляться с пункта производства составят и в пункт потребления максимально возможное и число , соответственно и единиц продукта: ; 3. 4. Четвертая перевозка осуществляется с пункта т.к. в пункт потребления , (без учета первого, второго столбца и четвертой строки). . 5. Пятая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца, третьей и четвертой строки). . 6. Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки). Опорный план имеет вид: 10 5 1 3 11 10 Метод аппроксимации Фогеля При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость. Если минимальная стоимость одинакова для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке, соответсующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке). Пример Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи: (Здесь мы перенесли потребности в верхнюю строку для удобства построения плана). Рассмотрим задачу, приведенную для методов северо-западного угла и минимального элемента Решение: 10 20 10 2 3 4 7 8 15 1 1 1 11 6 10 1 1 8 9 3 3 3 4 4 - 5 - - 4 1 2 19 2 2 2 1 2 2 2 2 2 2 2 - 2 - - 2 - - - 21 1 1 - Опорный план имеет вид: 7 0 8 0 1 3 0 0 19 2 Метод двойного предпочтения В случае больших размерностей, эффективен способ определения первоначального опорного плана с помощью метода двойного предпочтения. В каждом столбце отмечают знаком клетку с наименьшей стоимостью. Затем тоже проделывают в каждой строке. В результате некоторые клетки имеют двойную отметку. В них находится минимальная стоимость как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая и рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам с единичной отметкой. Остальные перевозки распределяют по наименьшей стоимости. 1.4.4. Методы проверки опорного плана на оптимальность Потенциалы. Критерий оптимальности плана Итак, наша транспортная задача имеет вид: Распишем нашу задачу в векторной форме. Для этого введем векторы Тогда ограничения задачи (3) могут быть записаны в виде Как уже говорилось выше, одно из этих ограничений является лишним, и оно может быть вычеркнуто. Рассмотрим теперь двойственную задачу. Так как ограничений всего m + n, то и соответствующие переменные двойственной задачи обозначим так: (переменные, соответствующие первым m ограничениям) и (переменные, соответствующие последним n ограничениям). Тогда, учитывая вид векторов виде: и вид вектора , запишем двойственную задачу в следующем Величины называются потенциалами складов, а величины потенциалами пунктов потребления. - Так как одно из ограничений является лишним, то на самом деле одного из потенциалов нет. Для сохранения симметрии всех формул и обозначений можно просто полагать, скажем, . Пусть теперь - оптимальный опорный план транспортной задачи. Тогда, согласно теореме двойственности, должно выполняться условие Это и позволяет проверить оптимальность любого опорного плана. Сам алгоритм выглядит следующим образом: Один из потенциалов задается произвольно, скажем, полагается . Рассматривается система линейных уравнений вида для тех наборов индексов i , j , для которых и всех пунктов потребления. и , и находятся потенциалы Для всех остальных наборов индексов i , j (для которых условие всех складов ) проверяется . Если это условие выполняется для всех наборов индексов i , j , для которых , то рассматриваемый план является оптимальным. Если же, хотя бы для одной пары , то план не оптимален. Прежде, чем приводить пример, расскажем о том, как реализуется пункт 2 этого алгоритма, когда находятся потенциалы и Одна из величин или задается произвольно, например, полагается Затем рассматриваются уравнения вида Так как известно, то находятся . : для тех j , для которых для некоторого множества индексов . . Для этих индексов для тех рассматриваются уравнения вида: , которые больше нуля. Так как находятся величины известны, тот для некоторого множества индексов . Далее повторяются пункты 2 (движение по строкам) и 3 (движение по столбцам), пока не определятся все потенциалы. Пример Пусть имеется три склада с запасами и четыре пункта потребления с потребностями . Коэффициенты , определяющие стоимость перевозок, заданы матрицей: Пункты потребления С 3 5 4 5 л 1 2 4 3 д 1 5 6 3 к а ы Построим исходный опорный план методом северо-западного угла. Он имеет вид 2 3 3 4 2 6 .1 .9 .2 .8 .3 План имеет 6=3+4-1 компонент, поэтому он является невырожденным. Заметим, что для него транспортные расходы равны . Заготовим матрицу размером (в нашем случае размером 3 4), в которую впишем те коэффициенты , которые соответствуют ненулевым перевозкам нашего плана (смотрите следующую страницу). Далее действуем следующим образом: Полагаем . 3 5 2 4 6 Идем по строке. , следовательно ; , следовательно . Идем по столбцу. , следовательно . Идем по строке. , следовательно . Идем по столбцу. , следовательно Идем по строке. . 3 , следовательно . Таким образом, определились потенциалы всех пунктов  и складов и пунктов потребления. Теперь можно закончить заполнение этой таблицы, вписав в пустые клетки суммы , то есть суммы соответствующих потенциалов. В результате получим: 3 5 7 4 3 5 7 4 - 2 4 1 2 4 6 3 3 В ней жирным шрифтом помечены те нахождения потенциалов. Сравнивая с матрицей величин , которые использовались для мы видим, что условие оптимальности плана нарушено в двух местах - для и . Следовательно, построенный нами план перевозок не является оптимальным. 1.4.5. Алгоритм улучшения плана Сформулируем теперь алгоритм перехода к новому опорному плану, дающему меньшее значение функции потерь. Прежде, чем формулировать его в общем виде, покажем его основные моменты на том примере, который мы начали рассматривать. Вспомним, что ограничения двойственной задачи соответствовали тому, что , а выполнение условия говорило о том, что соответствующий вектор надо вводить в базис. Поэтому и выполнение условия о том, что вектор надо вводить в базис. говорит У нас условие выполнено в двух случаях - для принято вводить в базис тот вектор, для которого данном случае это вектор . и . Вообще максимально. В , но в учебных целях мы введем в базис вектор Введение в базис вектора означает, что мы должны запланировать какую-то перевозку из третьего склада в первый пункт потребления. Пусть величина этой перевозки равна θ. Поставим ее в клетку, соответствующую i =3, j =1. Тогда мы получим следующий план перевозок: 3.1 2 3.9 4.2 2.8 6.3 θ Но теперь у нас нарушился баланс запасов и потребностей  получилось, что из третьего склада вывозится , а в первый пункт потребления поступает . Необходимо восстановить баланс запасов и потребностей. Для этого поступают следующим образом: по ненулевым компонентам плана перевозок строят цикл вида столбец – строка – столбец – строка -...- строка (см. рисунок), который начинается и кончается на компоненте θ Теперь для восстановления баланса запасов и потребностей можно поступить очень просто: при движении по столбцу от имеющихся компонентов плана надо отнимать θ , а при движении по строке θ наоборот, прибавлять θ . В результате получится следующий план перевозок, уже сохраняющий баланс запасов и потребностей: 2- θ 3.1+ θ 3.9- θ 4.2+ θ θ 2.8- θ 6.3 С балансом всё в порядке, но теперь у нас стало компонент плана, а должно быть . Поэтому надо выбрать θ так, чтобы одна из бывших компонент обратилась в нуль, но все остальные компоненты остались положительными. Для этого θ надо взять равным минимальному из тех чисел, из которых θ вычитается. В нашем случае θ вычитается из чисел 2; 3.9; 2.8 . Минимальное из них есть 2 и поэтому надо взять θ =2. В результате получится новый опорный план следующего вида, в котором снова будет положенные ему компонент. 5.1 1.9 2 6.2 0.8 6.3 Вычисляя транспортные расходы для этого плана, мы получим , откуда видно, что по сравнению с исходным планом транспортные расходы уменьшились на 2 единицы. Опишем этот процесс в общем виде. Итак, пусть для некоторой пары индексов выполнено условие . Тогда вектор надо вводить в базис. Если таких векторов окажется несколько, то обычно вводят в базис тот вектор, для которого величина разности максимальна. Исходя из клетки строят цикл по ненулевым компонентам плана перевозок по маршруту столбец - строка - столбец - строка - ... - строка, который начинается и заканчивается в клетке доказывать следующие два утверждения: - такой цикл всегда может быть построен; - такой цикл единственный. Итак, пусть этот цикл имеет вид . Мы не будем Установим новый план перевозок вида Все остальные компоненты плана перевозок, не входящие в цикл, остаются неизменными. Наконец, выберем θ таким образом, чтобы одна из новых компонент плана обратилась в нуль, а все остальные остались положительными. Для этого θ следует взять в виде , где считается . В результате получится новый опорный план. Покажем, что этот новый опорный план дает меньшее значение транспортных расходов, чем старый план. Так как компоненты плана, не входящие в цикл, не изменяются, то их можно не учитывать. Для ненулевых компонент исходного плана выполнялось условие и поэтому Для нового плана перевозок мы имеем В выражении, стоящем в квадратных скобках, большинство слагаемых сокращается и окончательно получаем так как мы вводим перевозку, для которой . Ну, а дальнейшее очевидно: надо повторять все итерации до тех пор, пока не будет получен оптимальный план. В силу конечности числа вершин допустимой области, это может быть сделано за конечное число шагов. Закончим наш учебный пример. Одну итерацию мы уже проделали. Вторая итерация Этап 1. Определение потенциалов и проверка оптимальности плана. Обычно это совмещается в одной таблице и выглядит в виде таблицы, приведенной на следующей странице. Сначала в таблицу выписываются , соответствующие ненулевым компонентам плана. Для наглядности их можно как-то помечать, скажем, обводить рамкой (в книге они отмечены жирным шрифтом). 2 5 7 4 2 5 7 4 -1 2 4 1 -3 -1 1 4 6 3 Затем определяются потенциалы. Обычно это легко сделать в уме, двигаясь по строкам и столбцам. Затем оставшиеся клетки заполняются суммами соответствующих потенциалов, то есть величинами . Наконец, производится сравнение получившейся таблицы с таблицей величин и определяются те клетки, где . Этап 2. Из тех пар индексов, где , находится та пара, где разность максимальна (в нашем случае это пара i =1, j =3). Строится цикл, определяется  и строится новый опорный план. В нашем случае эти преобразования имеют следующий вид: 5.1- θ θ 5.1 1.9+ θ 6.2- θ 2 θ 0.8 6.3 7 1.1 2 0.8 6.3 В нашем случае , так что новый опорный план нарисован в таблице справа. Значение транспортных расходов уменьшилось на величину , то есть на 15.3 единицы. Следующая итерация дается без пояснений. Третья итерация Этап 1 -1 2 4 1 -1 2 4 1 -1 2 4 1 2 1 4 6 3 В данном случае для всех клеток таблицы выполняется условие , что говорит о том, что план перевозок, полученный на предыдущей итерации, является оптимальным. Для этого плана перевозок значение транспортных расходов . По сравнению с исходным планом, полученным методом северо-западного угла, транспортные расходы уменьшились на 17.3 единицы, то есть на 21%. Сформулируем теорему. Теорема Если все запасы и все потребности целые числа, то оптимальный план перевозок тоже целочисленный. 1.4.6. Снятие вырожденности Эпсилон-прием При решении транспортных задач, особенно тогда, когда и - целые числа, часто приходится сталкиваться с вырожденными опорными планами, то есть с планами, число положительных компонент которых меньше . Это бывает тогда, когда, как уже указывалось выше, какое-то подмножество складов удовлетворяет потребности какого-то подмножества пунктов потребления. Для борьбы с этим неприятным явлением существует очень простой прием, который, в качестве профилактики, рекомендуется применять всегда, когда запасы продукта на складах и потребности пунктов потребления - целые числа. Он состоит в следующем: пусть запасы продукта есть пунктов потребления есть самыми , а потребности . Рассмотрим новую задачу с теми же , для которой с некоторым ε >0. Можно взять ε конкретным, но достаточно малым числом, а можно просто оставить в алгебраическом виде как букву. Затем транспортная задача решается обычным путем, а в ответе просто полагается ε =0, (или полученный результат округляется, если ε было взято конкретным малым числом). Пример Пусть матрица стоимостей перевозок имеет вид: 1 2 3 4 4 3 2 1 1 2 2 1 Запасы складов равны равны. . Потребности пунктов потребления Заметьте, что в данном случае , или , то есть имеются подгруппы складов, полностью удовлетворяющие потребности некоторых пунктов потребления. Чтобы снять намечающееся вырождение, будем решать задачу с теми же самыми , но с Дальнейшее дается с минимальными пояснениями. Построение исходного опорного плана. Используя метод северо-западного угла, получим следующий исходный опорный план 4 2+ ε 4- ε 4+2 ε 4-2 ε 6+3 ε Для этого плана значение функции потерь равно Первая итерация Этап 1. Определение потенциалов и проверка оптимальности плана. 1 2 1 0 1 2 1 0 1 1 3 2 1 1 2 3 2 1 План не является оптимальным. Отмечены те элементы, для которых Для ввода в базис выбран вектор . . Этап 2. Строим цикл, находим ε и переходим к новому опорному плану. 2+ ε + ε 2ε 6- ε 4- ε 4- ε - ε 4+2 ε + ε 4-2 ε - ε ε 6+3 ε 4-2 ε 8 6+3 ε ε В данном случае . Обратите внимание на то, что если бы было ε =0, то построенный план имел бы всего 4 положительных компоненты, то есть он был бы вырожденным. Вторая итерация Этап 1. Находим потенциалы и проверяем оптимальность плана. 1 2 1 1 1 2 1 1 2 3 2 2 1 1 2 1 1 Полученный план снова не является оптимальным. Условие нарушается на элементе с i =2, j =4. Цикл нарисован заранее. Этап 2 6- ε + ε ε 6 2ε-ε ε-ε 8 ε 6+3 ε - ε 8 ε 4- ε 6+2 ε 4-2 ε + ε В данном случае был бы вырожденным. . Опять-таки, если бы было ε =0, то план Третья итерация Этап 1. Нахождение потенциалов и проверка на оптимальность. Соответствующая таблица приведена ниже. 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 В данном случае для всех клеток таблицы выполнено условие что построенный план является оптимальным. , так Чтобы получить решение исходной задачи, надо положить ε =0. Тогда мы получим: ε 6 6 8 ε 4- ε 8 6+2 ε 4 6 Найденный оптимальный план имеет всего 4 компоненты, то есть он является вырожденным. Для него значение транспортных потерь равно то есть значение транспортных издержек уменьшилось по сравнению с планом, построенным по методу северо-западного угла , на 4 единицы. или на 9.5%. 2. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ 2.1. Классификация задач целочисленного линейного программирования. Примеры задач целочисленного линейного программирования При решении многих задач нецелочисленное решение не имеет смысла. Раздел математического программирования, в котором на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений, называется дискретным программированием. При наличии условия целочисленности имеется в виду подраздел дискретного программирования - целочисленное программирование. В экономике много задач с физической неделимостью объектов, предметов и факторов расчета. К примеру, нельзя построить 1,7 здания, 6,1 завода, 1,07 автомобиля, произвести 1,7 замера, осуществить 3,4 путешествия, купить 4,5 туристических путевок. Рассмотрим следующие задачи. Задача о рюкзаке Контейнер оборудован m отсеками вместимостью видов продукции для перевозки n . Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, ... единиц. Пусть - расход i-го отсека для перевозки единицы j-ой продукции. Обозначим через полезность единицы j-ой продукции. Требуется найти план перевозки, при котором максимизируется общая полезность рейса. Модель задачи примет вид: при ограничениях на вместимости отсеков условии неотрицательности условии целочисленности . - целые Когда для перевозки имеется один отсек и каждый вид продукции может быть взят или нет, то модель задачи принимает вид: . Задача о назначении Имеет n исполнителей, которые могут выполнять n различных работ. Известна полезность , связанная с выполнением i-м исполнителем j-й работы . Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должне быть закреплен только один исполнитель. Математическая модель задачи примет вид: Каждый исполнитель назначается только на одну работу: На каждую работу назначается только один исполнитель: Условия неотрицательности и целочисленности , . Задача коммивояжера Коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути. Математическая модель задачи: Условия неотрицательности и целочисленности , . Добавляется условие прохождение маршрута через все города, т.е. так называемое условие цикличности. Иначе, маршрут должен представлять собой замкнутую ломаную, без пересечений в городах-точках. Целочисленные и частично целочисленные задачи линейного программирования Определение 2.1. Экстремальная задача линейного программирования, в которой на решение налагается целочисленность компонент, является задачей целочисленного программирования и называется целочисленной задачей. Определение 2.2. Экстремальная задача линейного программирования, в которой на решение налагается целочисленность нескольких компонент, является задачей целочисленного программирования и называется частично целочисленной задачей. 2.2. Метод Гомори. Метод ветвей и границ Методы отсечения и их сущность Рассмотрим общую задачу целочисленного программирования в постановке: - целые . Назовем эту задачу - -задачей. Задачу без учета целочисленности назовем -задачей. Рассмотрим теорему. Теорема 2.1. Пусть G- многогранник, - множество его целых точек, R- выпуклая линейная оболочка множества 1) 2) 3) , тогда: -целочисленный многогранник; ; - множество опорных планов задачи многограннике содержится в . Общий алгоритм метода Гомори Определение 2.3. Правильное отсечение - отсечение, которое удовлетворяют следующим требованиям: 1. линейно; 2. отсекает часть области, не содержащей допустимых решений целочисленной 3. -задачи не отсекает ни одного целочисленного оптимального плана. Этап 1. Решается - задача, соответствующая исходной задаче. Если -задача не имеет решения, т.е. G пуста или неограниченна в положительном направлении возрастания (убывания) F, то устанавливается неразрешимость целочисленной задачи. Этап 2. Оптимальное решение -задачи проверяется на целочисленность. Если решение целочисленное, то задача решена. В противном случае, если условие целочисленности не выполняется хотя бы по одной координате, то переходят к третьему этапу. Этап 3. Дополнительное ограничение, которое 1. линейно; 2. отсекает часть целочисленной 3. области, не содержащей допустимых решений - задачи; не отсекает ни одного целочисленного оптимального плана, который входит в систему ограничений. Процесс построения дополнительных ограничений продолжается до тех пор, пока не получится целочисленный план или же установится отсутствие целочисленного решения задачи. Метод ветвей и границ Пусть - целые . Как и при решении задачи методом Гомори, первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи. Если среди компонент плана имеются дробные числа, то необходимо осуществить переход к новым планам, пока не будет найдено решение задачи. Метод ветвей и границ основан на предположении, что наш оптимальный нецелочисленный план дает значение функции, большее, чем всякий последующий план перехода. Пусть переменная в плане – дробное число. Тогда в оптимальном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу целому числу , либо больше или равно ближайшему большему . Определяя эти числа, находим симплексным методом решение двух задач :линейного программирования - целые . - целые . и Возможны четыре случая при решении этой пары задач: 1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции дают решение исходной задачи. 2. Одна из задач неразрешима, а другая имеет нецелочисленный оптимальный план. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу и строим две задачи, аналогичные предыдущим. 3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции от планов и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и дает искомое решение. 4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда рассматриваем ту из задач, для которой значение целевой функции является наибольшим. И строим две задачи. Алгоритм метода ветвей и границ 1. Находим решение задачи линейного программирования без учета целочисленности. 2. Составляет дополнительные ограничения на дробную компоненту плана. 3. Находим решение двух задач с ограничениями на компоненту. 4. Строим в случае необходимости дополнительные ограничения, согласно возможным четырем случаям получаем оптимальный целочисленный план либо устанавливаем неразрешимость задачи. Пример - целые . Решение: Находим решение без учет целочисленности задачи симплексным методом. , . Рассмотрим следующую пару задач: Зад ача №1 и Задача № 2 Первая задача имеет оптимальный план , вторая – неразрешима. Проверяем на целочисленность план первой задачи. Это условие не выполняется, поэтому строим следующие задачи: Задача №1.1 и Задача № 1.2 Задача № 1.2 неразрешима, а задача № 1.1 имеет оптимальный план , на котором значение целевой функции В результате получили, что исходная . задача программирования имеет оптимальный план и целочисленного . 3. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 3.1. Общая задача нелинейного программирования В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции f  x1 , x 2 ,  , x n  (1) при условии g i  x1 , x 2 , , x n  bi , i 1, k   g i  x1 , x 2 , , x n  bi , i k  1, m  , (2) где f и g i - некоторые известные функции n переменных, а bi - заданные числа. Класс задач нелинейного программирования шире класса задач линейного программирования. Подробное изучение практических задач, которые условились считать линейными, показывает, что они в действительности яв- ляются нелинейными. Существующие методы позволяют решать узкий класс n задач, ограничения которых имеют вид g i  x1 , x 2 ,  x n   aij x j j 1  i 1, m  , а целевая   функция является сепарабельной (суммой n функций  j x j ), или квадратической. Даже если область допустимых решений - выпуклая, то в ряде задач целевая функция может иметь несколько локальных экстремумов. С помощью большинства же вычислительных методов можно найти точку локального оптимума, но нельзя установить, является ли она точкой глобального (абсолютного) оптимума или нет. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой, и кроме глобального оптимума могут существовать точки локального оптимума. 3.2. Метод множителей Лагранжа Рассмотрим частный случай общей задачи нелинейного программирования (1) (2), предполагая, что система ограничений (2) содержит только уравнения, отсутствуют условия неотрицательности переменных, f  x1 , x 2 , , x n  и g i  x1 , x 2 ,  x n  - функции, непрерывные вместе со своими частными производными. Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных. Вводят набор переменных 1 ,  2 ,  ,  n , называемых множителями Лагранжа, и составляют функцию Лагранжа m F  x1 , x 2 ,  x n   f  x1 , x 2 , , x n    i  bi  g i  x1 , x 2 , , x n   i 1 , находят частные производные F  j 1, n , F  i 1, m  x j i и рассматривают систему n+m уравнений m g  F f   i i 0, j 1, n   x  j x j i 1 x j   F b  g  x , x ,  , x  0, i 1, m i i 1 2 n  i (3) с n+m неизвестными x1 , x 2 , , x n , 1 ,  2 , ,  n . Решив систему уравнений (3), получают все точки, в которых функция (1) может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (3), как правило, имеет несколько решений. 3.3. Выпуклое программирование Определение: Функция f  x1 , x 2 , , x n  , заданная на выпуклом множестве X,  1  2 называется выпуклой, если для любых двух точек X и X из X и любого 0  1 выполняется соотношение       f X  2   1    X 1 f X  2   1    f X 1 . (4) Определение: Функция f  x1 , x 2 , , x n  , заданная на выпуклом множестве X,  1  2 называется вогнутой, если для любых двух точек X и X из X и любого 0  1 выполняется соотношение      f X  2   1    X 1 f X  2   1    f X 1  (5) Если неравенства (4) и (5) считать строгими и они выполняются при 0  1 , то функция f  x1 , x 2 , , x n  является строго выпуклой (строго вогнутой). Выпуклость и вогнутость функций определяется только относительно выпуклых множеств. k f  x   f j  x  j 1 Если , где f j  x  , - выпуклые (вогнутые) функции на некотором n выпуклом множестве X  E , то функция f(x) - также выпуклая (вогнутая) на X. Основные свойства выпуклых и вогнутых функций: 1. Множество точек минимума выпуклой функции, заданной на выпуклом множестве, - выпукло. 2. Пусть f(x) - выпуклая функция, заданная на замкнутом выпуклом множестве X  E n . Тогда локальный минимум f(x) на X является и глобальным. 3. Если глобальный минимум достигается в двух различных точках, то он достигается и в любой точке отрезка, соединяющего данные точки. 4. Если f  x  - строго выпуклая функция, то ее глобальный минимум на выпуклом множестве X достигается в единственной точке. 5. Пусть функция f(x) - выпуклая функция, заданная на выпуклом множестве X, и, кроме того, она непрерывна вместе со своими частными производными  0 первого порядка во всех внутренних точках X. Пусть X - точка, в которой   f X  0  0 . Тогда в точке X  0  достигается локальный минимум, совпадающий с глобальным минимумом. 6. Множество точек глобальных (следовательно, и локальных) минимумов выпуклой функции f  x  , заданной на ограниченном замкнутом выпуклом множестве X, включает хотя бы одну крайнюю точку; если множество локальных минимумов включает в себя хотя бы одну внутреннюю точку множества X, то f  x  является функцией-константой. Задача выпуклого программирования Рассмотрим задачу нелинейного программирования f  x1 , x 2 ,  , x n   max (6) при ограничениях g i  x1 , x 2 ,  , x n  bi , i 1, m , x j 0, j 1, n . (7) (8) Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций f(x) и g i  x  , разработаны эффективные методы их решения. Говорят, что множество допустимых решений задачи (6) - (8) удовлетворяет условию регулярности, или условию Слейтера, если существует, по крайней  0 мере, одна точка X , принадлежащая области допустимых решений такая, что g i  X  0    bi , i 1, m . Задача (6) - (8) называется задачей выпуклого программирования, если функция f  x1 , x 2 , , x n  является вогнутой (выпуклой), а функции g i  x1 , x 2 , , x n   i 1, m  - выпуклыми. Функцией Лагранжа задачи выпуклого программирования (6) - (8) называется функция m L x1 , x 2 , , x n , y1 , y 2 ,  , y m   f  x1 , x 2 ,  , x n    y i  bi  g i  x1 , x 2 ,  .x n   i 1 , где y1 , y 2 , , y m - множители Лагранжа. Точка  X , Y   x1 , x 2 , x n , y1 , y 2 , y m  называется седловой точкой функции Лагранжа, если  0  0 L x1 , x 2 , , x n , y10 , y 20 , , y m0   L x10 , x 20 , , x n0 , y10 , y 20 ,  , y m0   L x10 , x 20 ,  , x n0 , y1 , y 2 ,  y m  для всех x j 0  j 1, n  и y i 0  i 1, m  . Теорема 1 (Куна - Таккера): Для задачи выпуклого программирования (6) - (8), множество допустимых решений которой обладает свойством регулярности, X  0   x10 , x 20 ,  , x n0  является оптимальным решением тогда и только тогда, когда  0  0  0 существует такой вектор Y  y1 , y 2 , , y n   y i 0, i 1, m  , что  X ,Y  седловая точка функции Лагранжа. Если предположить, что функции f и g i непрерывно дифференцируемы, то теорема Куна - Таккера может быть дополнена аналитическими выражениями, определяющими необходимые и достаточные условия того, чтобы точка  X   ,Y    была седловой точкой функции Лагранжа, т. е. являлась решением задачи выпуклого программирования:  L0  x 0, j 1, n ;  j  0 L0 0, j 1, n ; x j  x j  x 0 0, j 1, n ;  j   L0 0, i 1, m ;  y  i  0 L0  y i y 0, i 1, m ; i   y i0 0, i 1, m , L0 x j L0 и yi значения соответствующих частных производных функции где Лагранжа, вычисленных в седловой точке. 3.4. Квадратичное программирование Частным случаем задачи нелинейного программирования является задача квадратичного программирования, в которой ограничения g i  x1 , x 2 , , x n  bi  n a ij x j , i 1, m j 1 , являются линейными, а функция f  x1 , x 2 , x n  представляет собой сумму линейной и квадратичной функции (квадратичной формы) f ( x1 , x 2 ,  , x n ) c1 x1  c 2 x 2    c n x n  d11 x12  d 22 x 22    d nn x n2  2d12 x1 x 2  2d13 x1 x3    2d n 1n x n 1 x n Как и в общем случае решения задач нелинейного программирования, для определения глобального экстремума задачи квадратичного программирования не существует эффективного вычислительного метода, если не известно, что любой локальный экстремум является одновременно и глобальным. Так как в задаче квадратичного программирования множество допустимых решений выпукло, то, если целевая функция вогнута, любой локальный максимум является глобальным; если же целевая функция - выпуклая, то любой локальный минимум также и глобальный. Функция f представляет собой сумму линейной функции (которая является и выпуклой, и вогнутой) и квадратичной формы. Если последняя является вогнутой (выпуклой), то задачи отыскания максимума (минимума) целевой функции могут быть успешно решены. Вопрос о том, будет ли квадратичная форма вогнутой или выпуклой, зависит от того, является ли она отрицательноопределенной, отрицательно-полуопределенной, положительно-определенной, положительно-полуопределенной или вообще неопределенной 3.5. Градиентные методы Используя градиентные методы, можно найти, решение любой задачи нелинейного программирования. Применение этих методов в общем случае позволяет найти точку локального экстремума. Поэтому более целесообразно использовать их для нахождения решения задач выпуклого программирования. Процесс нахождения решения задачи с помощью градиентных методов k состоит в том, что начиная с некоторой точки X осуществляется последовательный переход к некоторым другим точкам до тех пор, пока не будет найдено приемлемое решение исходной задачи. Градиентные методы могут быть подразделены на две группы. К первой группе относятся методы, при использовании которых исследуемые точки не выходят за пределы области допустимых решений задачи. В данном случае наиболее распространенным является метод Франка - Вульфа. Ко второй - методы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Однако в результате реализации итерационного процесса находится точка области допустимых решений, определяющая приемлемое решение. Наиболее часто используются метод штрафных функций и метод Эрроу - Гурвица. При нахождении решения задачи градиентными методами итерационный процесс продолжается до тех пор, пока градиент функции f  x1 , x 2 , x n  в  k 1 очередной точке X не станет равным нулю или же пока не выполнится неравенство     f X  k 1  f X  k    , где   0 (точность полученного решения). Метод Франка - Вульфа. Пусть требуется найти максимальное значение вогнутой функции f  x1 , x 2 , x n  (9) при условиях n a ij x j bi , i 1, m j 1 x j 0, j 1, n , (10) (11) Ограничения содержат только линейные неравенства. Эта особенность является основой для замены в окрестности исследуемой точки нелинейной целевой функции линейной, в результате чего решение исходной задачи сводится к последовательному решению задач линейного программирования. Процесс нахождения решения начинают с определения точки, принадлежащей k области допустимых решений. Пусть это точка X . Вычисляют в этой точке градиент функции (9):       f X  k  f X  k  f X  k  f X  k   ; ; ; x 2 x n  x1      , строят линейную функцию Fk        f X  k  f X  k  f X  k  x1  x2    xn x1 x 2 x n . (12) Находят максимум функции (12) при ограничениях (10) и (11). Пусть решение k данной задачи определяется точкой Z . За новое допустимое решение  k 1 исходной задачи принимают координаты точки X , которые находят по формулам X  k 1  X  k    k  Z  k   X  k   , где  k - некоторое число, называемое шагом вычислений  0   k  1 . За  k   df X  k 1 0 принимают наименьший корень уравнения d k или выбирают произвольно, если он не принадлежит интервалу (0; 1). Метод штрафных функций. Рассмотрим задачу нелинейного программирования (6) -(8), где g i  x1 , x 2 , , x n  выпуклые функции. Вместо того, чтобы решать эту задачу, находят максимум функции F  x1 , x 2 ,  , x n   f  x1 , x 2 ,  , x n   H  x1 , x 2 ,  , x n  , где H  x1 , x 2 , , x n  определяется системой ограничений и называется штрафной функцией. Последнюю можно построить различными способами. Наиболее часто она имеет вид m H  x1 , x 2 ,  , x n   ai  x1 , x 2 , , x n  g i  x1 , x 2 ,  , x n  i 1 где , 0, если bi  g i  x1 , x 2 ,  x n  0, ai  x1 , x 2 , , x n   1, если bi  g i  x1 , x 2 ,  x n   0, а ai  0 - некоторые постоянные числа, представляющие собой весовые коэффициенты. Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое решение. Координаты последующей точки находят по формуле    m   f X  k  g X  k  x jk 1 max 0; x jk       ai i x j  i 1  x j       , где  - шаг вычислений  0    1 . Итерационный процесс обычно начинают при сравнительно малых значениях ai и, продолжая его, эти значения постепенно увеличивают. Метод Эрроу - Гурвица. При нахождении решения задачи нелинейного программирования методом штрафных функций значения ai , выбирают произвольно, что приводит к значительным колебаниям удаленности определяемых точек от области допустимых решений. Этот недостаток устраняется при решении задачи k методом Эрроу - Гурвица, согласно которому на очередном шаге числа ai находят по формуле ai k  max 0; ai k 1  g i  X  k   , i 1, m  0 В качестве начальных значений ai берут произвольные неотрицательные числа. Пример решения задачи квадратичного программирования методом Франка-Вульфа Задача. Найти максимум вогнутой функции Решение. Найдем градиент функции . В качестве X(0)=(0, 0). Δf(X(0))=(2, 4)≠0.│f(X(k+1))−f(X(k+1)))│≤0,01. 1- итерация. Δf(X(0))=(2, 4). Получили задачу линейного программирования. Решаем ее графически. Z(0)=(0, 4), X(1) = X(0) + λ0(Z(0) − X(0)) = (0, 0) + λ0((0, 4) − (0, 0)) = (0, 0) + λ0(0, 4). x(1)1=0, x(1)2=4λ0. Подставляем полученные значения x(1)1 и x(1)2 в целевую функцию, получим f( λ0) = 16λ0 − 32λ20→max, f' = 16 − 32λ0= 0, λ0=0,25. Следовательно, X(1) =(0, 1), f(X(1))=2. Проверим условие окончания │f(X(1))−f(X(0)))│=│2 − 0│= 2 > 0,01. Условие не выполняется, следовательно, переходим к следующей итерации. 2-я итерация. Δf(X(1))=(2, 0). F1(X) = 2x1+0x2→ max. Решая графически получили Z(1) =(6,4; 0,8), X(2) = X(1) + λ1(Z(1) − X(1)) = (0, 1) + λ1((6,4; 0,8) − (0, 1)) = (0, 1) + λ1(6,4; -0,2). x(2)1=6,4λ1, x(2)2=1−0,2λ1. Подставляем полученные значения x(2)1 и x(2)2 в целевую функцию, получим f( λ1) = 2 +12,8λ1 − 46,76λ21→max, f' = 12,8 − 93,52λ1= 0, λ1≈0,15. Следовательно, X(2) =(0,96; 0,97), f(X(2))=2,9966. Проверим условие окончания │f(X(2))−f(X(1)))│=│2,9966 − 2│= 0,9966 > 0,01. Условие не выполняется, следовательно, переходим к следующей итерации. 3-я итерация. Δf(X(2))=(0,08; 0,12). F2(X) = 0,08x1+0,12x2→ max. Решая графически получили Z(2) =(6,4; 0,8), X(3) = X(2) + λ2(Z(2) − X(2)) = (0,96; 0,97) + λ2((6,4; 0,8) − (0,96; 0,97)) = (0,96; 0,97) + λ2(5,44; -0,17). x(3)1=0,96+5,44λ2, x(3)2=0,97−0,17λ2. Подставляем полученные значения x(3)1 и x(3)2 в целевую функцию, получим f( λ2) = 2,9966 +0,4188λ2 − 29,6514λ22→max, f' = 0,4188 − 59,3028λ2= 0, λ2≈0,007. Следовательно, X(3) =(0,99808; 0,96881), f(X(3))=2,99805. Проверим условие окончания │f(X(3))−f(X(2)))│=│2,99805 − 2,9966│= 0,00145 < 0,01. Условие выполняется, следовательно, целевая функция достигает своего максимального значения в точке X*=X(3) =(0,99808; 0,96881) и равна f*=f(X(3))=2,99805.