«Рекомендовано УМО по специальностям педагогического образования для студентов вузов по специальности 030100 Информатика. 1 Электронная PDF-версия издания подготовлена в 2011 году для сайта кафедры ТИДМ математического ...»

В. А. Горелик, Т. П. Фомина

«Основы исследования операций: Учебное пособие»

Москва, МПГУ, 2004

Рекомендовано УМО по специальностям педагогического образования для

студентов вузов по специальности 030100 Информатика.

1

Электронная PDF-версия издания подготовлена в 2011 году для сайта кафедры ТИДМ математического факультета МПГУ — http://tidm.ru 2

ВВЕДЕНИЕ

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

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

Исследование операций — это раздел прикладной математики, который занимается построением математических моделей анализа реальных задач и процессов управления и принятия решений (экономических, социальных, технических, военных и др.). Он структурно оформился в период второй мировой войны и включает в себя ряд разделов, отличающихся друг от друга различными математическими моделями различных задач поиска оптимальных решений. Математическая модель нужна для детального предварительного анализа реального явления. Математика проводит количественный и качественный анализ модели, помогает предсказать, как поведёт себя система в различных условиях и даёт рекомендации для принятия «наилучшего» решения.

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

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

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

• разработка необходимых и достаточных признаков оптимальности в различных классах задач;

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

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

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

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

Настоящее пособие адресовано студентам, обучающимся по различным специальностям, учебные планы которых включают дисциплину «Исследование операций». В более полном объеме оно может найти применение в обучении студентов по специальности 030100 Информатика и по специальности 010200 Прикладная математика. А также может оказаться полезным преподавателям, различным специалистам, желающим ознакомиться с основами исследования операций.

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ

§ 1.1. Математическая модель операции Изложение любого предмета начинается с определения или описания используемых в нем основных понятий. В исследовании операций естественно надо начинать с самого понятия «операция».

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

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

Оперирующей стороной (ОС) называется совокупность лиц, которые стремятся в данной операции к поставленной цели.

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

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

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

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

Неконтролируемые факторы, исходя из информированности о них исследователя операции, можно разбить на три группы:

а) фиксированные;

б) случайные;

в) неопределенные.

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

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

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

Ход операции можно описать некоторым набором фазовых переменных 1 t,, k t. Степень соответствия хода операции поставленной цели в математической модели характеризуется критерием эффективности W, который представляет собой некоторую функцию, зависящую от фазовых переменных, стратегий и неконтролируемых факторов. В математической модели эквивалентом цели операции является требование максимизации критерия эффективности.

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

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

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

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

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

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

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

Пример (планирование суточного выпуска продукции).

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

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

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

цель – максимизация дохода от продажи выпущенных за сутки изделий двух видов;

принятие решения для ОС состоит в определении суточных объёмов выпуска каждого из двух видов изделий;

возможности ОС ограничены временными ресурсами эксплуатации станков трёх видов.

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

В нашем примере известными являются следующие параметры:

суточная норма bj эксплуатации станка j, j 1,2,3;

время aij обработки единицы изделия вида i (i=1,2) на станке типа j (j=1,2,3);

стоимость ci (продажи) единицы изделия вида i (i=1,2).

Все эти параметры являются неуправляемыми (неконтролируемыми) факторами, т.к. они заданы, то это фиксированные неконтролируемые факторы.

Неизвестными или искомыми являются следующие величины:

объём суточного выпуска изделия вида i (i=1,2).

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

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

xi – объём суточного выпуска изделия вида i (i=1,2).

а время, необходимое для обработки x1, x2 единиц изделий на станке j, есть a1 j x1 a2 j x2 ( j 1,2,3).

Теперь первоначальную задачу можно сформулировать математически:

Это есть задача математического (линейного) программирования с целевой функцией c1 x1 c 2 x 2 и множеством допустимых решений X, которое описывается неравенствами. Критерий оптимальности здесь полностью задается требованием максимизации целевой функции, что определяет отношение предпочтения.

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

изучение условия задачи;

определение важнейших факторов;

выделение известных и неизвестных параметров;

выявление управляемых и неуправляемых факторов;

дополнение условия задачи недостающими сведениями;

введение системы обозначений;

составление математической модели (математическое выражение целевой (целевых) функции и соотношений и связей между параметрами);

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

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

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

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

Для того чтобы иметь возможность сравнивать стратегии, удобнее всего иметь численную оценку каждой стратегии. Оценка, ставящая в соответствие каждой стратегии х действительное число, т.е. являющаяся функцией переменной х, называется оценкой эффективности стратегии. Если имеется только фиксированный неконтролируемый фактор, т.е. у принимает известное исследователю операции значение у0, то критерий эффективности W=F(x,y0) является функцией только х. Введем обозначение f0(х)=F(x,y0). Величина f0(х) может служить оценкой эффективности стратегии. При этом стратегия х1 лучше стратегии х2, если f0(х1)> f0(х2). Естественным образом определяется в этом случае и наилучшая или оптимальная стратегия. Это такая стратегия х0, для которой выполняется соотношение (при наличии только фиксированных неконтролируемых факторов стратегиифункции не имеют смысла, поэтому пространство стратегий может включать лишь стратегии-константы, такое пространство стратегий принято обозначать через Х).

Пусть теперь имеются случайные или неопределенные факторы. В этом случае для фиксированной стратегии х* критерий эффективности W=F(x*, y) является функцией от у, а не фиксированным числом, и значит не может служить оценкой эффективности. Каждой стратегии уже соответствует не одно, а несколько значений критерия эффективности и результат сравнения стратегий с помощью критерия оказывается неопределенным.

Рассмотрим вопросы построения оценок эффективности, которые, вообще говоря, могут вводиться различным образом. Определение вида оценки эффективности и связанного с ней понятия (принципа, критерия) оптимальности представляет собой элемент постановки задачи и является, в конечном счете, правом оперирующей стороны. Однако существуют наиболее распространенные и обоснованные оценки эффективности, зависящие от вида неконтролируемых факторов. Если имеется случайный неконтролируемый фактор, представляющий собой случайную величину с известным исследователю операции законом распределения, то в качестве оценки эффективности чаще всего используется математическое ожидание критерия эффективности. Пусть неконтролируемый фактор у принимает n значений у1, …, уn c вероятностями р1, …, рn, тогда математическое ожидание определяется по формуле Значит, в качестве оценки эффективности стратегии берется функция Такая оценка эффективности называется оценкой в среднем, так как значение случайной величины в каждом конкретном случае может существенно отличаться от математического ожидания и только среднее значение реализаций случайной величины при большом числе испытаний приближается к нему. При использовании этой оценки имеется определенный риск получения в каждом конкретном случае меньшего результата, чем тот, на который рассчитывали, и в этом надо отдавать себе отчет. Только в среднем при многократном проведении данной операции мы можем с достаточной уверенностью рассчитывать на получение при использовании некоторой стратегии результата, равного оценке в среднем этой стратегии. Таким образом, в рядовой операции, повторяющейся много раз, указанный риск оправдан, но в единичной операции вряд ли на него можно пойти. Это значит, что использование статистических данных в единичных (уникальных) ситуациях фактически ничего не дает и неконтролируемые факторы при этом надо считать неопределенными, но это уже другой случай.

При наличии случайных неконтролируемых факторов могут использоваться и стратегии-функции, если у оперирующей стороны ожидается дополнительная информация. Тогда в качестве оценки эффективности также обычно используется математическое ожидание только надо иметь в виду, что при определении математического ожидания, когда производится осреднение по у, необходимо учитывать зависимость Оценке эффективности в среднем соответствует понятие оптимальности в среднем: ~ 0 оптимальна в среднем на пространстве стратегий X, если где f c (x ) определяется из (1.5).

В частности, для стратегий-констант x 0 оптимальна в среднем на пространстве стратегий X, если Перейдем теперь к случаю неопределенных неконтролируемых факторов. Относительно неопределенного неконтролируемого фактора у исследователю операции известна только область его возможных значений Y, поэтому при применении стратегии х он может ожидать, что критерий примет произвольное значение в замкнутом интервале от А = min F ( x, y ) до В = max F ( x, y ) (для простоты будем считать, что максимумы и минимумы функций существуют, в противном случае надо использовать верхние и нижние точные грани, т.е. супремумы и инфимумы, и там, где необходимо, вводить понятия приближенных —оптимальных стратегий). Значит оценка эффективности стратегии х по смыслу должна принадлежать отрезку [А, В].

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

Этой оценке соответствует понятие оптимальной гарантирующей стратегии, т.е. такой x 0, для которой или Аналогично вводятся понятия гарантированной оценки эффективности и оптимальности в гарантированном смысле для стратегий-функций:

Величина называется максимальным гарантированным результатом на множестве X (аналогично на Х ). В математике такое выражение принято называть максиминами или при перестановке процедур максимизации и минимизации — минимаксами.

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

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

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

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

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

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

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

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

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

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

Линейное программирование (включая целочисленное программирование), нелинейное программирование (включая выпуклое программирование) и динамическое программирование составляют основные подразделы математического программирования. В настоящем пособии им посвящены, соответственно, главы 3, 4 и 5.

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

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

Среди задач исследования операций со случайными неконтролируемыми факторами наиболее важными являются задачи массового обслуживания, задачи теории надежности и задачи управления запасами. Эти задачи характеризуются определенным видом критериев эффективности, пространств стратегий и фигурирующих в них случайных величин, которые отражают их содержательный смысл. Массовому обслуживанию (включенному в программу) посвящена глава 9 настоящего пособия. Два других раздела можно изучать факультативно [7,9,16,33].

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

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

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

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

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

Основными видами оценки принимаемых решений в условиях риска являются:

• ожидаемое значение результата (математическое ожидание);

• ожидаемое значение результата в сочетании с минимизацией его дисперсии;

• доверительный интервал для получаемого результата;

• наиболее вероятное событие (исход) в будущем.

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

1. Фирмой "Супертранзистор'' выпускаются радиоприемники трех различных моделей: А, В и С. Каждое изделие указанных моделей приносит доход в размере 8, 15 и 25 единиц соответственно. Необходимо, чтобы фирма выпускала за неделю не менее 100 приемников модели А, 150 приемников модели В и 75 приемников модели С.

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

Так, в частности, в расчете на 10 приемников модели А требуется 3 ч для изготовления соответствующих деталей, 4ч на сборку и 1ч на упаковку. Соответствующие показатели в расчете на 10 приемников модели В равняются 3, 5 и 1.5 ч, а на 10 приемников модели С - 5, 7 и 3. В течение ближайшей недели фирма может израсходовать на производство радиодеталей 150 ч, на сборку 200 ч и на упаковку 60 ч.

Постройте оптимизационную модель, максимизирующую прибыль.

2. Авиакомпания "Небесный грузовик", обслуживающая периферийные районы страны, располагает 8 самолетами типа 1, 15 самолетами типа - 2, самолетами типа 3, которые она может использовать для выполнения рейсов в течение ближайших суток. Грузоподъемность (в тысячах тонн) известна: для самолетов типа 1, 7 для самолетов типа 2, 4 для самолетов типа 3.

Авиакомпания обслуживает города А и В. Городу А требуется тоннаж в 20000 т, а городу В - в 30000 т. Избыточный тоннаж не оплачивается. Каждый самолет в течение дня может выполнить только один рейс.

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

Постройте оптимизационную модель, минимизирующую расходы.

3. Фирма «Микродеталь» является владельцем мелкосерийного металлообрабатывающего завода. Дневной портфель заказов включает n деталей, каждая из которых может обрабатываться на n различных станках. Пусть tij общая продолжительность обработки детали i на станке j (включая время наладки станка).

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

4. Задача о доставке грузов (задача о покрытии). Фирма "Автопегас" должна доставить грузы пяти своим клиентам в течение рассматриваемого дня. Клиенту А нужно доставить груз весом в 1 единицу, клиенту В - в 2 единицы, клиенту С - в 3 единицы, клиенту D - в 5 единиц и клиенту Е - в 8 единиц. Фирма располагает четырьмя автомашинами следующей грузоподъемности: машина 1 - 2 единицы, машина 2 - 6 единиц, машина 3 - 8 единиц, машина 4 - 8 единиц. Стоимость эксплуатации автомашины j составляет сj.

Предположим, что одна машина не может доставлять груз обоим клиентам А и С, аналогично одна машина не может использоваться для доставки груза обоим клиентам В и D.

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

5. Предприятие производит изделия трех видов, поставляет их заказчикам и реализует на рынке. Заказчикам требуется 100 изделий первого вида, 200 изделий второго вида и 250 изделий третьего вида. Условия спроса на рынке ограничивают число изделий первого вида 200 единицами, второго — 300 и третьего — 500 единицами. Для изготовления изделий используется типа ресурсов. Количество ресурсов, потребляемых для производства одного изделия, общее количество ресурсов и прибыль от реализации одного изделия заданы в таблице.

Как организовать производство, чтобы обеспечить заказчиков, не допустить затоваривания и получить максимальную прибыль? Постройте оптимизационную модель, объясните ее элементы и соотношения.

6. Предприятие рекламирует свою продукцию с использованием телевидения, радио, газет. Анализ рекламной деятельности в прошлом показал, что эти средства приводят к увеличению прибыли соответственно на 10, 5 и усл.ед. в расчете на 1 усл.ед., затраченную на рекламу. Администрация предприятия на рекламу выделила 50 тыс.усл.ед. и не намерена тратить на телевидение более 40%, на радио и газеты — более 60% от общей суммы выделенных средств.

Постройте оптимизационную модель, максимизирующую прибыль, объясните ее элементы и соотношения.

Глава 2. КЛАССИЧЕСКИЕ ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ § 2.1. Основные понятия теории экстремальных задач При наличии только фиксированных неконтролируемых факторов задача поиска оптимальных решений сводится к экстремальной задаче. Если при этом на выбор стратегии не накладывается ограничений (что на практике встречается редко) или ограничения имеют вид только равенств, то применимы классические методы оптимизации. Эти методы и рассматриваются вкратце в данной главе.

Исходными данными при постановке задачи поиска экстремума является множество X и определенная на нем функция f(x). Мы будем рассматривать конечномерные задачи, поэтому x является вектором произвольной размерности n, т.е. x = (x1,…, xn), а множество X подмножеством евклидова пространства Rn (возможно совпадающим со всем пространством). Помимо задания X (его называют допустимым множеством) и f (x) (ее называют целевой функцией) необходимо определить, что понимается под решением задачи. Во-первых, речь может идти о нахождении точек максимума (одной или всех), минимума (одной или всех) или тех и других. Во-вторых, необходимо уточнить само понятие максимума (минимума), так как оно может пониматься в глобальном и локальном смысле.

Определение. Точка x*X называется точкой глобального (абсолютного) максимума функции f (x) на множестве X, если Определение. Точка x*X называется точкой локального максимума функции f(x) на множестве X, если > 0 такое, что где U (x*) - -окрестность точки x* (шар радиусом с центром в x*).

Определения глобального и локального минимумов получаются заменой в (2.1) и (2.2) знаков неравенств на противоположные.

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

Если x* есть точка глобального максимума f(x) на X, то будем использовать запись т.е. под max f(x) понимается максимальное (абсолютное) значение f(x) на X. Для точки глобального максимума принято обозначение Частным решением задачи поиска максимума называется нахождение одной точки x* и значения f(x*), определяемых (2.3), (2.4). Полным решением называется нахождение величины max f(x) и всех реализующих ее значений аргумента, множество которых принято обозначать Обычно, если это не оговаривается особо, под решением задачи максимизации будем понимать нахождение ее частного решения (глобального).

Аналогичные понятия и обозначения используются для задачи поиска глобального минимума (соответственно min f(x), arg min f(x), Arg min f(x)).

Множество всех точек локальных максимумов включает в себя множество (2.5), но, вообще говоря, с ним не совпадает. Задачу нахождения всех локальных максимумов мы будем записывать в виде Аналогично для локальных минимумов а для задачи нахождения всех локальных экстремумов (максимумов и минимумов) Так как, очевидно, точки максимума функции f(x) совпадают с точками минимума функции –f(x), то все свойства и методы решения задачи (2.6) легко переносятся на (2.7), (2.8) (мы будем их рассматривать на примере задачи максимизации).

Экстремальные задачи принято делить на задачи поиска безусловного и условного экстремума. Если X = Rn, т.е. рассматриваются точки экстремума f(x) на всем n-мерном пространстве, то имеем задачу на безусловный экстремум (или без ограничений). Если X Rn (собственное подмножество n-мерного пространства), то имеем задачу на условный экстремум (или с ограничениями). Терминология эта возникла в связи с тем, что множество X в последнем случае обычно задается какими-то условиями (обычно ограничениями вида равенств и неравенств). В классическом анализе рассматриваются задачи без ограничений и с ограничениями типа равенств.

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

Теорема Вейерштрасса. Если X компакт в Rn (замкнутое ограниченное множество), f(x) непрерывная на X функция, то точки глобального максимума и минимума f(x) на X существуют.

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

Поэтому полезной является следующая ее модификация.

Следствие. Если X замкнутое непустое множество в Rn, f(x) непрерывная на X функция и ограничено множество где c некоторая константа, меньшая верхней грани f(x) на X, то точка глобального максимума f(x) на Х существует.

Доказательство. Множество P является по определению непустым подмножеством множества X, оно ограничено, а в силу непрерывности f(x), и замкнуто. Поэтому по теореме Вейерштрасса существует точка глобального максимума f(x) на P со значением не меньше c. Но на множестве X\P выполняется f(x) < c, следовательно, данная точка является и глобальным максимумом f(x) на X, что и требовалось доказать.

Для существования глобального минимума в определении (2.9) множества P знак неравенства следует заменить на противоположный, а константа c должна быть больше нижней грани f(x) на X.

Для рассматриваемых в дальнейшем экстремальных задач будет предполагаться, как правило, выполнение условий теоремы Вейерштрасса или ее следствия. Условие ограниченности множества P может заменяться на условие f(xk) – при | xk | (для минимума f(xk) ).

§ 2.2. Условия экстремума в задачах без ограничений Задача поиска безусловного экстремума (без ограничений) имеет вид Классические необходимые условия экстремума (локального или глобального, максимума или минимума) для этой задачи дает Теорема Ферма. Пусть функция f(x) дифференцируема в точке решения задачи (2.10) x*, тогда Доказательство. По определению дифференцируемой функции многих переменных для любого вектора hRn имеем статочно малое положительное число, 0(d) величина более высокого порядка малости, нежели d, скалярное произведение векторов f(x*) и h.

Предположим противное утверждению (2.11), т.е. что |f(x*)| 0. Тогда из (2.12) при достаточно малых d имеем f(x*+ dh) > f(x*) при h = f '(x*) и f(x*+ dh)< f(x*) при h = - f(x*), что противоречит определению экстремумов.

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

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

Пусть задана квадратная симметрическая матрица A = (aij) размера nn. Рассмотрим скалярное произведение, где первым вектором является произведение матрицы A на n-мерный вектор h (мы не будем делать различия в обозначениях между вектор-строкой и вектор-столбцом, считая всегда, что вектор задан в такой форме, которая позволяет производить соответствующую операцию умножения на него матрицы).

матрицы A, hi компоненты вектора h, т.е. матрица A задает квадратичную форму. Квадратичная форма называется положительно определенной, если Аналогично вводятся понятия неотрицательной, неположительной и отрицательной определенности (в (2.14) знак > меняется соответственно на для любого hRn.

Доказательство. Используя разложение функции многих переменных в ряд Тейлора до квадратичных членов, имеем f(x*+dh)=f(x*)+d < 0 для любого ненулевого hRn, удовлетворяющего условиям = 0, то h2 любое, h1=0, < L"xxh, h >= h2 >0, значит, (1, 0) точка локального минимума со значением f = 1.

Откуда следует, что критическая точка r= 3 V / 2 есть точка минимума.

Функция S(r) непрерывна в интервале (0; +). Поэтому согласно свойству непрерывных функций единственный минимум функции S в интервале (0; +) совпадает с ее наименьшим значением в этом интервале.

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

Неравенство между средним арифметическим и средним квадратическим Средним арифметическим чисел x1,…, xn называется, как известно, величина тельства неравенства xi2 – B = 0. Эта задача регулярна и в соответствии с принципом Лании гранжа ее решение удовлетворяет системе уравнений (другая точка минимум). Значит что и требовалось доказать (заметим, что неравенство превращается в равенство только в случае, когда все xi равны между собой).

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

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

По этим данным нужно восстановить функциональную зависимость y=f(x), описывающую работу устройства. Уточним постановку задачи. Пусть априори известен класс возможных функциональных зависимостей f(x,d1,…,dk) с точностью до параметров d1,…,dk. По методу наименьших квадратов конкретное значение вектора параметров d =(d1,…,dk) выбирается так, чтобы минимизировать сумму квадратов невязок в измерениях, т.е.

величину Рассмотрим для простоты линейную зависимость Тогда и надо найти абсолютный минимум этой величины как функции аргументов а и b. Условие экстремума дает систему из двух линейных уравнений Определитель этой системы Естественно считать, что не все xi равны между собой, поэтому из доказанного неравенства между средним арифметическим и средним квадратическим имеем D > 0. Значит, система имеет единственное решение Матрица вторых производных есть Ее главный минор первого порядка равен 2 xi2, а главный минор второго порядка равен 4D, т.е. они положительны (если не все xi равны между собой). Значит, по критерию Сильвестра матрица положительно определена и в силу теоремы о достаточных условиях экстремума точка (а*, b*) доставляет минимум величине (по крайней мере, локальный).

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

В теории информации количество информации в сообщении о значении величины, которая может принимать априори n значений с вероятностями p1,…, pn, принято определять величиной Для этого имеется ряд оснований, связанных со свойствами функции Н (обычно эти свойства постулируются как аксиомы и однозначно определяют вид Н). В частности, количество информации в сообщении о значении величины, принимающей априори два значения с равными вероятностями, равно единице (оно и принимается за единицу измерения информации, называемую битом). Для представления единицы информации достаточно одного разряда ячейки памяти машины, работающей с двоичными числами. Поставим вопрос: сколько двоичных разрядов достаточно для представления информации о величине, принимающей n возможных значений с неизвестными вероятностями. Другими словами, какое максимальное количество информации может содержать сообщение о величине с n возможными значениями. Для ответа на этот вопрос надо найти максиn учитывать, что pi 0, i 1, n ). Функция Н не определена при pi = 0, поэтому доопределим ее по непрерывности при pi 0. Используя правило pi0 1, pi 0, i i0 полагаем H = 0 (так как Н 0, то это минимальное значение). Для нахождения максимума составим функцию Лагранжа Получим систему уравнений откуда видно, что все pi равны между собой, т.е.

Для нахождения глобального максимума, который существует в силу теоремы Вейерштрасса, надо это решение сравнить с граничными точками pi=0, но на границах Н = 0.

Значит, очевидно, точка,..., доставляет глобальный максимум Н со значением log2n. Это и есть искомое максимальное количество информации. Например, при n=8 требуется три разряда.

1. Найти оптимальное распределение ограниченного ресурса в а единиц между n потребителями, если прибыль, получаемая при выделении j-му потребителю x j единиц ресурса, вычисляется по формуле c j x j.

2. Завод А расположен на расстоянии а км от железной дороги, идущей в город В, и на расстоянии b км от города В. Под каким углом к железной дороге следует провести шоссе с завода А, чтобы доставка грузов была наиболее дешевой, если стоимость перевозок по шоссе в k раз дороже, чем по железной дороге?

3. Найти прямоугольник наименьшего периметра, ограничивающий заданную площадь, используя теорему о среднем.

4. Составляется электрическая цепь из двух параллельно соединенных сопротивлений. При каком соотношении между этими сопротивлениями сопротивление всей цепи r максимально, если при последовательном соединении этих сопротивлений оно равно R?

5. Поперечное сечение открытого канала имеет форму равнобедренной трапеции. При каком наклоне боков «мокрый периметр» сечения будет наименьшим, если площадь «живого сечения» воды в канале равна S, а уровень воды равен h?

6. По плану производства продукции предприятию необходимо изготовить 180 изделий, которые могут быть изготовлены двумя технологическими способами. При производстве х1 изделий первым способом затраты составляют 4х1 x12 руб., а при изготовлении х2 изделий вторым способом они равны 8х2+ x 22 руб. Определить, сколько изделий каждым из способов следует изготовить, так чтобы общие затраты на производство продукции были минимальны.

7. Фирма реализует автомобили двумя способами: через торговых агентов и магазин. При реализации х1 автомобилей через торговых агентов расходы на реализацию составляют 4 х1 х12 ден.ед., а при продаже х 2 автомобилей через магазин расходы составляют х 22 ден.ед. Найти оптимальный способ реализации автомобилей, минимизирующий суммарные расходы, если общее число предназначенных для продажи автомобилей составляет 200 штук.

8. Производственная функция фирмы имеет вид y x10.25 x 2.5, лимит на ресурсы равен 18 ед., цены на ресурсы соответственно равны 3 и ден.ед. Решите задачу максимизации выпуска фирмы, используя условия первого и второго порядков для функции Лагранжа.

Глава 3. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ § 3.1. Постановка задачи линейного программирования В последние десятилетия появился ряд классов экстремальных задач, к которым классические методы непосредственно оказались неприменимыми. Многие из них связаны с практическими проблемами техники, экономики, экологии и т.д. Характерным для таких задач является наличие ограничений в форме неравенств, большое количество переменных и ограничений, недифференцируемость целевых функций или функций ограничений, невыполнение тех или иных условий регулярности, что в классической математике не рассматривалось. В теоретическом плане классические результаты могут быть распространены на некоторые из этих случаев, но часто они становятся малоэффективными или вообще практически неприменимы. Поэтому появилась потребность в разработке новых идей и методов решения экстремальных задач, что привело к формированию новой области математики математического программирования. Наиболее простым и широко используемым является аппарат линейного программирования, относящийся к случаю линейных целевых функций и функций ограничений. Рассмотрим сначала несколько примеров.

Транспортная задача. Пусть имеется m складов S1,…, Sm, предназначенных для хранения некоторого товара, и n пунктов потребления этого товара P1,…, Pn. Надо составить наиболее экономичный план перевозок товара со складов в пункты потребления. Исходными данными являются запасы товаров на складах a1,…, am, потребности пунктов потребления b1,…,bn и стоимости перевозок единицы товара cij с каждого склада Si в каждый пункт потребления Pj, i= 1, m, j= 1, n. Будем предполагать выполненным условие удовлетворения всех потребностей:

Произвольный план перевозок представляется матрицей X = (xi j) размера m x n, где xij количество товара, направляемого со склада Si в пункт потребления Pj.

Множество допустимых планов задается следующими ограничениями:

условиями неотрицательности перевозок условиями ограниченности товара на складах условиями удовлетворения потребностей пунктов потребления В силу условия (3.1) множество Х, очевидно, не пусто. Точками этого множества являются матрицы, элементы которых удовлетворяют условиям (3.2) - (3.4). Требуется выбрать из множества Х такую точку (матрицу), которая минимизирует общую стоимость перевозок, т.е. целевую функцию вида Заметим, что если стоимости перевозок единицы товара с любого склада на любой пункт потребления отличны от нуля, т.е. cij > 0, то для оптимального плана перевозок, минимизирующего функцию (3.5), неравенства (3.4), очевидно, будут выполняться как равенства, поэтому ограничения (3.4) можно заменить на ограничения что по существу не изменит задачу. Если условие (3.1) представляет собой равенство т.е. имеет место баланс наличия товара и потребности в нем, то тогда, очевидно, и ограничения (3.3) выполняются в виде равенств Это следует из того, что если в (3.3) или (3.4) хотя бы одно из ограничений представляет собой строгое неравенство, то, просуммировав m+n неравенств, придем к противоречию с равенством (3.7).

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

Задача о рационе кормления. Пусть имеется возможность производить n видов кормов К1,…, Кn для животноводческой фермы. Каждый из этих видов кормов характеризуется определенным набором полезных свойств (калорийность, содержание перевариваемого протеина, витаминных добавок и т.д.). Обозначим эти свойства буквами Н1, …, Нm. Будем предполагать, что для каждого вида кормов Кj известно содержание в единице веса всех указанных компонент Нi, т.е. калорий, протеина, витаминов и т.д. Обозначим эти характеристики кормов буквами aij, i= 1, m, j= 1, n. Матрица A=||aij|| размера m x n полностью характеризует все виды кормов. Предположим, что известна годовая потребность фермы по всем компонентам Н1, …, Нm, задаваемая вектором b= (b1,…, bm), а также вектор стоимости кормов с=(с1,…, сn), где cj стоимость единицы корма вида Кj.

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

Рацион кормления можно описывать вектором x = (x1,…, xn), где xj количество корма вида Кj, поставляемое на ферму в течение года. Он должен, во-первых, удовлетворять условию неотрицательности Во-вторых, должна быть обеспечена потребность во всех полезных компонентах. Для фиксированного х содержание компоненты Нi в рационе равно a ijxj, поэтому должны выполняться ограничения Целевая функция (стоимость всех кормов) имеет вид Задача заключается в минимизации (3.11) при ограничениях (3.9), (3.10).

Более кратко ее можно записать в матричной форме:

Задача планирования производства. Пусть имеется m видов ресурсов R1,…, Rm, которые могут быть использованы для производства n видов товаров T1,…, Tn. Для производства единицы товара Tj необходимо затратить aij количества ресурса Ri, i= 1, m, j= 1, n. Матрица A = || aij || называется технологической матрицей. Известна цена cj на товар Tj и общее количество ресурсов b1,…, bm. Векторы b = (b1,…, bm), c = (c1,…, cn) называются, соответственно, векторами ресурсов и цен.

Требуется выбрать такой план производства x = (x1,…, xn), который в условиях заданных ограничений на ресурсы максимизирует валовое производство (стоимость выпущенной продукции). Здесь xj производимое количество товара вида Tj.

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

или в матричной записи Задача состоит в максимизации (3.13) при условиях (3.12).

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

В линейном программировании, как и вообще в экстремальных задачах, задача минимизации может быть сведена к задаче максимизации, и наоборот, если в качестве целевой функции новой задачи взять целевую мизации cj =-cj, j= 1, n.

Каждое ограничение типа меньше или равно в задаче линейного программирования можно заменить на ограничение типа больше или равно путем умножения на –1. Таким образом, ограничение эквивалентно где a ij= - a ij, j= 1, n, b i = - bi.

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

Ограничение типа равенства можно заменить на два противоположных ограничения типа неравенства. Так, ограничение эквивалентно двум ограничениям где a ij = - aij, b i = - bi, j= 1, n.

Если в задаче линейного программирования имеется переменная, на которую не наложено условие неотрицательности, то ее можно заменить на две неотрицательные переменные путем преобразования вида Если переменная xj ограничена снизу не нулем, а некоторой константой d, то путем замены переменных можно перейти к неотрицательной переменной x/j.

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

Стандартная форма задачи линейного программирования:

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

при ограничениях В матричной записи условие (3.20) имеет вид Общая форма задачи линейного программирования:

при ограничениях Все сказанное выше, естественно, относится и к этим трем формам, т.е. они легко переводятся одна в другую. Стандартная форма является частным случаем общей при k = m, r = n, каноническая при k = 0, r = n.

Общая переводится в стандартную путем замены m – k равенств на 2(m – k) неравенств, а в каноническую путем замены k неравенств на k равенств с помощью k свободных переменных. Аналогично стандартная форма переводится в каноническую, и наоборот.

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

а) допустимых планов нет, т.е. множество допустимых планов пусто, тогда задача не имеет решения;

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

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

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

Для этого достаточно привести соответствующие примеры:

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

В примере а) неотрицательность переменных означает, что множество допустимых планов должно лежать в неотрицательном ортанте. Линейное неравенство x1 + x2 -1 определяет полуплоскость, лежащую ниже прямой, задаваемой аналитически уравнением x1 + x2 = -1. Эта полуплоскость не имеет общих точек с неотрицательным ортантом, значит, множество допустимых планов пусто и задача не имеет решения.

В примере б) множество допустимых планов Х представляет собой пересечение неотрицательного ортанта и полуплоскости, лежащей выше прямой, определяемой уравнением x1 – x2 = 1. В отличие от предыдущего примера это множество непусто, но не ограничено.

Линии уровня целевой функции x1 + x2, на которых она принимает постоянные значения, изображены на рисунке пунктирными прямыми, стрелка указывает направление роста. Очевидно, на множестве Х эта функция сверху не ограничена, значит задача не имеет решения. Впрочем, не следует думать, что неограниченность множества допустимых планов обязательно влечет за собой отсутствие решения. Если в примере б) изменить только целевую функцию на –(x1 + x2), то задача будет иметь решение x10 x2 0 (направление роста функции изменится на противоположное, и линия наивысшего уровня на множестве Х будет проходить через начало координат).

В примере в) множество допустимых планов Х представляет собой пересечение неотрицательного ортанта и двух полуплоскостей, ограниченных сверху прямыми, задаваемыми уравнениями Так как множество Х замкнуто и ограничено, а целевая функция непрерывна, то по теореме Вейерштрасса задача имеет решение. Линия наивысшего уровня функции x1 + x2 на многоугольнике Х проходит через вершину с координатами x10 x2 13. Это и есть решение задачи.

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

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

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

Определение. Множество Х n-мерного евклидова пространства называется выпуклым, если вместе с любыми двумя точками x1, x2 X ему принадлежит весь отрезок, соединяющий эти точки, т.е. любая точка x = dx1 + (1 – d)x2, где 0 d 1, принадлежит Х.

Круг, треугольник, куб, полупространство являются примерами выпуклых множеств, а кольцо, например, не является выпуклым множеством.

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

Доказательство. Рассмотрим задачу линейного программирования в стандартной форме (3.17) (3.19). Если x1, x2 X, то x1 0, x2 0, Ax1 b, Ax2 b. Рассмотрим точку x = dx1 + (1 - d)x2, 0 d 1. Очевидно, x 0 и Ax= dAx1 + (1–d)Ax2 db + (1–d)b = b, т.е. x X. Для любой другой формы задачи линейного программирования доказательство легко получить либо непосредственно, как для стандартной формы, либо путем перехода к стандартной форме. Лемма доказана.

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

Определение. Множество Х n-мерного евклидова пространства называется замкнутым, если оно содержит все свои предельные точки, т.е.

такие точки, в каждой окрестности которых имеются точки из Х.

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

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

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

Определение. Точка х выпуклого множества Х называется угловой (или крайней), если не существует таких точек x1, x2 X, x1 x2, что x=dx1+ +(1-d)x2 при некотором d(0,1).

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

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

Рассмотрим некоторые важные свойства выпуклых множеств.

Теорема отделимости. Для любого выпуклого замкнутого множества Х и любой точки y, не принадлежащей Х, существует разделяющая их гиперплоскость, т.е. существует такой вектор a 0, что Доказательство. Рассмотрим функцию расстояния от фиксированной точки y до произвольной точки xX: (x, y)= |x - y|. Эта функция непрерывна по х, ограничена снизу (нулем), значит на замкнутом множестве Х существует х 0, реализующая нижнюю грань этой функции (точка х называется проекцией точки y на Х).

Возьмем в качестве вектора a= х 0 - y0. Так как = > 0, С другой стороны, в силу (3.25) для любой точки z X Если xX, то в силу выпуклости Х точка Подставив выражение для z в (3.27), имеем или Из последнего неравенства, сокращая равные члены, имеем Последнее возможно лишь при (в противном случае при d 0 приходим к противоречию). Значит Из (3.26) и (3.28) получаем утверждение теоремы.

Геометрически теорема означает, что можно выбрать такую гиперплоскость, что множество Х и точка y лежат в разных полупространствах, определяемых этой гиперплоскостью (см. рисунок). Для этого надо взять построенный при доказательстве теоремы вектор а и число b, удовлетворяющее условию Гиперплоскость, определяемая уравнением =b, отделяет y от Х.

Теорема об опорной гиперплоскости. В любой граничной точке х выпуклого замкнутого множества Х существует опорная гиперплоскость, т.е. существует вектор a 0 и число b такие, что < a, х 0 > = b, < Доказательство. Рассмотрим последовательность точек yk, не принадлежащих Х, такую, что yk х 0 (так как х 0 — граничная точка Х, то такая последовательность существует). По теореме отделимости для каждого yk существует ak 0 такое, что Вектора a могут быть пронормированы | a |=1, поэтому существует (в силу ограниченности) Переходя к пределу в (3.29), имеем Осталось положить b=< a, х 0 >, и теорема доказана.

Теорема о представлении. Любая точка х 0 выпуклого замкнутого ограниченного множества X может быть представлена в виде выпуклой (линейной) комбинации конечного числа угловых точек этого множества.

Доказательство. Проведем его по индукции по наименьшей размерности n евклидова пространства Rn, содержащего множество X.

Если n=1, то X является отрезком и утверждение теоремы очевидно.

Предположим, что теорема справедлива для n-1 и докажем ее для n.

Пусть сначала х 0 — граничная точка X. Построим в этой точке опорную гиперплоскость. Множество Xo=X как пересечение выпуклого замкнутого ограниченного множества X с выпуклым замкнутым множеством из (n-1)-мерного пространства является выпуклым, замкнутым, ограниченным и принадлежит (n-1)-мерному пространству. По индуктивному предположению для х 0 X найдутся угловые точки x1,…, xk множества Xo такие, что Покажем, что x1,…, xk являются угловыми точками и для Х. Предположим противное, т.е. что для некоторой точки xi найдутся x/, x// X, x/ x//, d(0,1) такие, что xi=dx/+(1-d)x//. Так как xi Xo, то для определяющего вектора a а поскольку опорная к Х гиперплоскость, Так как 0 < d < 1, то Значит, x/, но x/ X, следовательно, x/ Xo=X. Аналогично доказывается, что x// Xo. Мы пришли к противоречию, так как xi угловая точка Xo.

Пусть теперь х 0 внутренняя точка X. Проведем через х 0 прямую l. Пересечение l X является отрезком, концы этого отрезка x/ и x// принадлежат границе множества X. Для них, как доказано, теорема верна, т.е.

существуют угловые точки y1,…, yk, z1,…, zr множества X такие, что Но х 0 = dx/ + (1-d)x//, где 0 < c, xi >, i = 1, k.

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

т.е. x Имеем суммируя эти неравенства для i= 1, k, получим что противоречит равенству (3.30).

Пусть теперь Х неограничено, х 0 оптимальный план. Возьмем доn мерного вектора х ). Обозначим через гиперплоскость, определяемую xi=М, а через L полупространство, определяемое нерауравнением венством Имеем х 0 X L и х 0. Множество X L выпукло, замкнуто, ограничено, поэтому существуют такие угловые точки этого множества x1,…, xr, что Без ограничения общности можно считать, что все di>0 (иначе соответствующие нулевым коэффициентам угловые точки можно исключить из линейной комбинации), тогда аналогично доказанному равенству (3.31) имеем Если хотя бы одна из точек xi является угловой для множества Х, то теорема доказана. Если же все xi не являются угловыми точками для X, то обязательно xi, i= 1, r. Действительно, если xi не является угловой для Х, то Значит, мы получили новый опорный план ~ с базисом a1,…, a i0 1, a,…, a, a, который доставляет большее значение целевой функции, чем исходный опорный план ( > 0), т.е. достигли поставленной цели.

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

III. Для всех k (m + 1 k n) выполнено ck – zk 0. Покажем, что в этом случае исходный план x является оптимальным.

Действительно, возьмем любой другой план x/ X. Он удовлетворяет системе m ограничений типа равенств, т.е.

Подставив в (3.41) представление всех векторов ak через базис a1,…,am (см.(3.37)), получаем С другой стороны, справедливо представление вектора b в виде (3.36), а так как вектора a1,…, am независимы, то эти представления должны совпадать, т.е.

Сравним теперь значения целевых функций. Так как коэффициент разложения векторов базиса по базису есть (каждый вектор базиса равен самому себе), для k= 1, m величины zk совпадают с сk, поэтому в данном случае справедливо сk – zk 0, k= 1, n. Далее, выполняются соотношения:

т.е.

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

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

Эта таблица на каждом шаге соответствует текущему базису опорного плана. В общем случае базис состоит из m вектор-столбцов матрицы коэффициентов A с произвольными номерами i1,…, im из номеров 1, …, n.

Элементами таблицы являются коэффициенты разложения векторстолбцов матрицы A по базису (обозначаемые x ik j ), коэффициенты разложения вектора ограничений b по базису, являющиеся компонентами опорного плана, соответствующего данному базису (обозначаемые для единообразия x ik 0 ), компоненты вектора коэффициентов линейной формы c с номерами i1,…, im, величины zj, j = 0, n, определяемые по формулам (z0 значение целевой функции для данного опорного плана), разности cj– zj, j= 1, n. Переход от одной симплексной таблицы к другой таблице следующего шага алгоритма происходит следующим образом.

Рассматривается последняя строка таблицы. Если cj – zj 0 для всех j= 1, n, то вектор x0 с компонентами x i1 0,, xim 0 на местах i1,…, im и с нулями на остальных местах является оптимальным планом, т.е. решение задачи найдено.

Если для некоторого j0 выполняется неравенство с j0 z j0 0 и для j0–го столбца таблицы справедливо x ik j0 0, k= 1, m, то целевая функция неограничена, т.е. задача не имеет решения.

Наконец, если для некоторого j0 выполняется с j0 z j0 0 и в столбце с номером j0 существует хотя бы один положительный элемент x ik j0 0 (1 k m), то можно получить лучший опорный план. Для этого выбираем j0 так, что (это позволяет добиваться на каждом шаге наибольшего возможного роста целевой функции и тем самым уменьшить число итераций), а 0 и i0 выбираем из условия Базис на следующем шаге получается путем замены в базисе данного шага вектор-столбца матрицы A с номером i0 на вектор-столбец с номером j0.

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

По формулам (3.43) вычисляются коэффициенты первых m строк новой таблицы (для всех j от 0 до n и всех k от 1 до m, здесь для единообразия положено b=a 0 ). Далее по формулам (3.42) рассчитывается (m+1)-я строка новой таблицы, определяются разности c – z, т.е. (m+2)–я строка, и процесс повторяется снова.

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

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

Без потери общности можно считать, что вектор ограничений b для задачи линейного программирования в канонической форме неотрицателен (иначе соответствующие ограничения типа равенств достаточно умножить на – 1). Рассмотрим вспомогательную задачу при ограничениях Планом этой задачи является (n+m)-мерный вектор Матрица коэффициентов этой задачи есть Так как b 0, план = (0, b) является допустимым (x = 0, и = b). Этому плану соответствует базис из m последних вектор-столбцов матрицы A/ (искусственный базис), образующих единичную подматрицу. Значит, является опорным планом, т.е. исходный опорный план для вспомогательной задачи (3.44), (3.45) строится легко и можно сразу применять для ее решения описанный выше итеративный процесс симплекс-метода. Пусть получено это решение Покажем, что если и* = 0, то x* опорный план исходной задачи линейного программирования в канонической форме, а если и* > 0, то исходная задача не имеет решения (вспомогательная задача всегда имеет решение, так как множество допустимых планов у нее непусто по крайней мере содержит, а целевая функция (3.44) ограничена снизу нулем). Действительно, если и*=0, то х* допустимый план исходной задачи, так как Ax* = b, а поскольку симплекс-метод состоит в переборе угловых точек множества допустимых планов, т.е. * угловая точка множества то, очевидно, х* угловая точка множества X = {x | Ax = b, x 0}, и мы получили опорный план исходной задачи х*. Если и* > 0, то значение вспомогательной задачи больше нуля (как и*i), а для любого допустиi мого плана исходной задачи xX можно построить допустимый план вспомогательной задачи = (x, 0), на котором целевая функция вспомогательной задачи принимает нулевое значение, значит в этом случае множество допустимых планов исходной задачи пусто, и она не имеет решения.

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

Рассмотрим для иллюстрации следующий пример:

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

при ограничениях Ее матрица коэффициентов имеет вид а исходный опорный план (0, 0, 0, 4, 6).

Впрочем, в данном случае опорный план нетрудно найти для исходной задачи непосредственно. Для этого возьмем, например, в качестве базиса два первых вектор-столбца матрицы A, т.е. положим x3 = 0 и получим опорный план Обозначим вектор-столбцы матрицы A по порядку a1, a2, a3. Текущий базис состоит из векторов a1 и a2, а вектор a3, как нетрудно заметить, представляется в виде Симплексная таблица на первом шаге имеет вид Мы видим, что разность с - z положительна для третьего столбца, значит, полученный план не является оптимальным, а так как в третьем целевой функции. Положительный элемент единственен и стоит в первой строке, значит из базиса надо вывести вектор a1 и ввести вектор a3 (на роль вводимого вектора мог претендовать только a3, но какой из векторов a1 или a2 следует выводить, заранее не очевидно).

Произведем пересчет по формулам (3.43), (3.42), вычислим с – z и получим новую симплексную таблицу В этой таблице все разности с – z неположительны, следовательно, найден оптимальный план x0 = 0,, 6 и максимум целевой функции z 0 = 20.

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

Рассмотрим задачу линейного программирования в стандартной форме (3.17) - (3.19).

Двойственной к ней называется задача при ограничениях Здесь A матрица, получающаяся транспонированием матрицы A, если матрица A имеет размер m x n, то x n-мерный вектор, а у m-мерный вектор.

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

Если задачу (3.46) - (3.48) преобразовать к стандартной форме и применить к ней правило построения двойственной задачи, то нетрудно убедиться, что после соответствующих преобразований получится задача (3.17) - (3.19).

Таким образом, можно сказать, что задачи (3.17) - (3.19) и (3.46) взаимодвойственные или просто двойственные задачи линейного программирования, но иногда, чтобы их различать, задачу (3.17) - (3.19) называют прямой, а (3.46) - (3.48) двойственной.

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

Рассмотрим в качестве примера построение двойственной задачи к задаче в канонической форме (3.17), (3.21), (3.19).

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

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

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

Вернемся к двойственным задачам (3.17) - (3.19) и (3.46) - (3.48). Для них справедливо следующее утверждение.

Теорема. Для любых допустимых планов x и у двойственных задач (3.17) - (3.19) и (3.46) - (3.48) выполняется неравенство Если для некоторых допустимых планов x и у этих задач выполняется равенство то x решение задачи (3.17) - (3.19), у решение задачи (3.46) - (3.48).

Доказательство. Пусть x и у произвольные допустимые планы двойственных задач, т.е. Ax b, x 0, Aту с, у 0. Тогда т.е. справедливо неравенство (3.49).

Пусть теперь x0 и у0 таковы, что выполняется (3.50). Возьмем произвольные допустимые планы x и у двойственных задач. В силу доказанного первого утверждения теоремы следовательно, x0 и у0 оптимальные планы двойственных задач. Теорема доказана полностью.

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

Теорема существования. Если задачи (3.17) - (3.19) и (3.46) - (3.48) имеют хотя бы по одному допустимому плану, то они обе имеют решения.

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

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

Теорема (о разделяющей гиперплоскости). Если X и Y выпуклые, замкнутые множества, не имеющие общих внутренних точек, то существует разделяющая их гиперплоскость, т.е. существуют такие ненулевой вектор a и скаляр d, что Доказательство. Рассмотрим множество, представляющее собой разность множеств X и Y, т.е.

Множество Z является, очевидно, выпуклым и замкнутым, а точка не является его внутренней точкой, т.е. либо вообще не принадлежит Z, либо является его граничной точкой. Применяя теорему отделимости (в первом случае) или теорему об опорной гиперплоскости (во втором случае), имеем, что существует такой вектор a 0, для которого Отсюда < a, x > < a, y > x, у и можно, очевидно, подобрать такое число d, что выполняется утверждение теоремы.

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

Теорема двойственности 1. Двойственные задачи линейного программирования (3.17) - (3.19) и (3.46) - (3.48) либо обе имеют решения x0 и у0, причем обязательно либо обе не имеют решения.

Доказательство. Пусть сначала существует решение x0 прямой задачи (3.17) - (3.19). Покажем, что существует решение двойственной задачи у0. Рассмотрим множество (m+1)-мерных векторов вида Множество это представляет собой область значений векторов c, x x o в (m+1)-мерном пространстве для всех x из неотрицательного ортанта n-мерного пространства.

Так как x0 решение задачи (3.17) - (3.19), то не могут одновременно выполняться неравенства b – Ax >0 и < c, x – x0> > 0, значит, множество P не имеет общих внутренних точек с неотрицательным ортантом применить доказанную выше теорему отделимости. Значит существуют такой вектор a 0 и скаляр d, что Относительно a и d можно утверждать, что a 0 и d = 0. Действительно, если хотя бы одна компонента a отрицательна, то, выбирая последовательность векторов qk из неотрицательного ортанта с неограниченно возрастающей данной компонентой и равными нулю всеми остальными компонентами, получим, что противоречит < a, q > d q.

Далее, 0R а значит, < a, p/ > 0, т.е. d 0, следовательно, d = 0, т.е. разделяющая гиперплоскость проходит через начало координат.

того, можно утверждать, что вектор a может быть выбран так, что am+1>0.

Это следует из того, что P есть многогранник и с гранью ортанта q1=…=qm=0 он может иметь только одну общую точку начало коордиm нат, поэтому разделяющая P и R гиперплоскость не обязана совпадать с этой гранью, но если гиперплоскость отлична от грани q1 = … = qm = 0, то у определяющего ее вектора (m+1)-я компонента отлична от нуля.

Итак, am+1 > 0, а так как уравнение определяемой вектором a разделяющей гиперплоскости < a, z >=0 и расположение “положительного” и “отрицательного” полупространств не изменяется от умножения вектора а на любое положительное число, то можно считать, что am+1 = 1.

Обозначим теперь вектор из первых m компонент вектора a через y и покажем, что y0 решение задачи (3.46) - (3.48). Имеем откуда Так как последнее неравенство справедливо для любого x 0, то A y c (в противном случае хотя бы одна из компонент вектора c – Aтy0 положительна и, выбирая вектор x с большой данной компонентой и нулевыми остальными, получим в левой части неравенства сколь угодно большое число, т.е. придем к противоречию).

Значит y0 0 и Ат y0 с, т.е. y0 допустимый план задачи (3.46) Положим теперь в неравенстве (3.51) x = 0, получим Но, с другой стороны, из (3.49) следует, что должно выполняться обратное неравенство, значит справедливо равенство (3.50), но отсюда, как было доказано, следует, что y0 решение задачи (3.46) - (3.48).

Таким образом, если прямая задача имеет решение, то и двойственная задача имеет решение, и экстремальные значения этих задач совпадают. Если двойственная задача не имеет решения, то и прямая задача не имеет решения, так как, предположив существование решения прямой задачи, мы получим по доказанному, что существует решение двойственной задачи, т.е. придем к противоречию. Но задачи (3.17) - (3.19) и (3.46) являются взаимодвойственными, т.е. разделение их на прямую и двойственную является чисто условным, поэтому аналогично справедливы утверждения, что если двойственная задача имеет решение, то и прямая имеет решение, и экстремальные значения этих задач совпадают, если двойственная задача не имеет решения, то и прямая не имеет решения.

Теорема доказана полностью.

Следующее утверждение называется второй теоремой двойственности (или теоремой о дополняющей нежесткости).

Теорема двойственности 2. Если x0 и y0 соответственно решения задач (3.17) - (3.19) и (3.46) - (3.48), то Доказательство. Рассмотрим скалярное произведение.

Так как y0 0, Ax0 b, то 0. С другой стороны, = - - = 0, значит, =0, т.е.

y i0 (bi a i j x 0j ) 0, откуда следует первое утверждение теоремы.

Аналогично, если рассмотреть < x0, Ат y0-c >, то, с одной стороны, в силу x0 0, Ат y0 c выполняется неравенство < x0, Атy0 – c > 0, а с другой стороны, значит =0 и справедливо второе утверждение теоремы.

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

Мы рассмотрим это на примере транспортной задачи.

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

Тогда задача сводится к минимизации (3.5) при ограничениях (3.6), (3.8), (3.2).

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

то матрица коэффициентов имеет вид (на остальных местах стоят нули).

Среди m + n ограничений типа равенств (3.6), (3.8) независимыми в силу условия баланса (3.7) являются не более m+n-1, значит можно положить равными нулю по крайней мере компонент и найти все остальные из уравнений (3.6), (3.8), т.е. базис для транспортной задачи состоит не более чем из m+n-1 векторов, а опорный план имеет не более чем m+n-1 ненулевых компонент.

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

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

Клетка на пересечении i-й строки и j-го столбца соответствует переменной xij, i= 1, m, j 1, n. Клетка в “северо-западном углу” соответствует переменной x11. Положим x11 min (a1, b1 ). Если при этом x11 a1, т.е. a1 b1, то весь запас товаров со склада S1 направлен в пункт потребления P1 и значит Если же x11 = b1, т.е. a1 b1, то потребности пункта потребления P1 удовлетворены и значит Таким образом, после первого шага с учетом изменений запаса товара на S1 и потребности в товаре P1 получим одну из двух таблиц Эти таблицы отличаются от начальной тем, что у них заполнены либо первая строка, либо первый столбец. Снова рассматриваем клетку в “северо-западном углу ”. Для таблицы 2 это клетка на пересечении второй строки и первого столбца; соответствующая переменная полагается равной x21 min (a2, b1 a1 ). Для таблицы 3 это клетка на пересечении первой строки и второго столбца; соответствующая переменная полагается равной x12 min (a1 b1, b2 ). В любом случае, заполняя нулями соответствующую строку или столбец, получаем таблицу, в которой заполнены либо две первые строки, либо два первых столбца, либо первая строка и первый столбец. Продолжая этот процесс до полного заполнения таблицы 1, получим, очевидно, допустимый план x*, причем нетрудно показать, что план x* является опорным.

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

Вектор y=(u1,…, um, v1,…, vn), являющийся допустимым планом двойственной задачи (3.53), (3.54), может иметь как положительные, так и отрицательные компоненты.

Из второй теоремы двойственности следует, что если x0 и y0 оптимальные планы задач (3.5), (3.6), (3.8), (3.2) и (3.53), (3.54), то т.е. либо x ij 0, либо u i0 v 0j cij (возможно одновременно). В данном случае оказывается, что это свойство можно использовать как признак оптимальности. Точнее, если x0 и y0 допустимые планы этих задач и если для индексов i, j, для которых x ij 0, выполняется u i0 v 0 c ij, то x0 оптиj мальный план транспортной задачи.

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

Переменные ui и vj двойственной задачи называются потенциалами складов Si и пунктов потребления Pj, а их суммы ~ij u i v j псевдостоис мостями перевозок. Таким образом, признаком оптимальности допустимого плана транспортной задачи x0 являются условия:

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

Алгоритм метода потенциалов состоит в следующем. Выбирается начальный опорный план x* транспортной задачи (например, методом “северо-западного угла”). Он имеет не более n+m-1 ненулевых компонент.

Обозначим множество пар индексов (i, j), для которых xij 0 через П*. Для определения m+n двойственных переменных u *, v*j, i 1, m, j 1, n, имеем сиi стему уравнений В системе (3.55) число уравнений меньше числа неизвестных, поэтому можно одно неизвестное положить равным нулю и легко найти последовательно все остальные. Далее, для пар индексов (i, j)П* проверяются неравенства Если *ij 0 (i, j ) П *, то данный опорный план x* является оптимальным. Если существует пара (i0, j0), для которой *i0 j0 0, то x* не является оптимальным и осуществляется переход к новому опорному плану, в котором переменная xi0 j0 уже будет базисной, т.е. будет осуществляться перевозка из S i0 в Pj0. Для простого определения такого опорного плана используется циклическая переброска. В таблице 1, заполненной компонентами предыдущего опорного плана x*, выбирается замкнутая ломаная линия, которая начинается и заканчивается в клетке (i0, j0), кроме этой клетки линия имеет вершины (точки излома) только в клетках, соответствующих базисным переменным плана x*, и в каждой вершине делает поворот на 900.

Пусть получилась последовательность пар индексов, соответствующих вершинам цикла, ( i0, j0), ( i1, j0),( i1, j1)…( i0, jk). Число членов этой последовательности, очевидно, четно.

(здесь для единообразия считается ik+1=i0).

Возьмем новый план, у которого компоненты, соответствующие нечетным членам построенной последовательности, больше соответствующих компонент плана x* на, компоненты, соответствующие четным членам последовательности, меньше на, а остальные равны компонентам плана x*. Новый план х является, очевидно, допустимым и опорным, он имеет одну новую базисную переменную x* j, а одна бывшая базисная переменная плана (на которой достигается минимум в (3.56)) в плане х равна нулю. При переходе от плана x* к плану х изменение целевой функции равно т.е. новый план лучше старого.

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

Для иллюстрации описанного процесса решения транспортной задачи рассмотрим численный пример и для него построим начальный опорный план по методу “северо-западного угла” и сделаем одну итерацию по методу потенциалов.

Пусть в транспортной задаче m=3, n=4, a1=20, a2=12, a3=8, b1=10, b2=15, b3=8, b4=7, а коэффициенты линейной формы проставлены в правых верхних углах клеток таблице 4, в которой методом “северо-западного угла” построен начальный опорный план.

Найдем теперь потенциалы. Уравнения (3.55) здесь имеют вид Положим u*1 = 0, получаем v*1=10, v*2=8, u*2=2, v*3=4, u*3=-1, v*4=6. Посчитаем псевдостоимости для внебазисных переменных Начальный опорный план не является оптимальным, так как, например, ~21 c 21. Сделаем x21 новой базисной переменной. Для построения ноc* вого опорного плана осуществим переброску по циклу из четырех клеток (2,1), (1,1), (1,2), (2,2) в количестве 5 (см. таблицу 4). При этом получим новый опорный план х, у которого x11 5, x12 15, x22 0, x 5, и уменьшим значение целевой функции на 35. Продолжая этот процесс, получим решение задачи (проделать в качестве упражнения).