Введение

Термин «исследование операций» (operations research), по-видимому, впервые появился в 1939 г. и, как научная дисциплина, сформировался во время второй мировой войны. Однако истоки этой отрасли науки можно обнаружить еще до первой промышленной революции.

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

Небольшие группы ученых, привлеченных высшим командованием Англии в период 1939-1940, добились значительных успехов в системе противовоздушной обороны Великобритании. После этого использование научных коллективов стало широко практиковаться в США, Канаде, Франции.

В Англии работа таких групп стала известна как операционные исследования (operational research), а в США – как наука об управлении, анализ операций, исследование операций, системный анализ и теория организационного управления.

После окончания второй мировой войны судьба этой научной дисциплины в Англии и США оказалась различной.

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

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

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

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

В 1957 г. была образована Международная федерация обществ исследования операций.

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

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

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

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

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

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

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

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

Отражение воздушного налета средствами ПВО.

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

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

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

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

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

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

Принципы построения сложных систем

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

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

Фундаментальный принцип конструирования систем состоит в максимизации математического ожидания эффективности и при­водит к необходимости исследования отношений «эффективность/ стоимость», и в процессе конструирования стремится либо максимизировать эффективность системы при фиксированной стоимости, либо минимизировать стоимость при фиксированном значении эффективности.

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

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

Роль математических моделей на различных этапах проектирования АСОиУ

Одной из важнейших особенностей системы обработки информации – тесная связь  с внешней средой, поэтому при разработке АСОиУ выделяют, как самостоятельные этапы:

¾     внешнее проектирование АСОиУ,

¾     внутреннее проектирование АСОиУ.

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

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

¾     единичная нить,

¾     большая нагрузка,

¾     состязательные ситуации.

 

 

Формулирование целей и критерия эффективности

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

¾     опрос высшего руководства организации заказчика;

¾     опрос компетентных представителей внешних организаций, связанных с заказчиком;

¾     анализ функционирования существующей системы.

Полученный перечень проверяют на предмет выявления взаимозависимых целей. Иногда такой анализ показывает, что одни цели являются по отношению к другим вспомогательные или же настолько тесно связаны, что достижение одной цели автоматически влечет за собой удовлетворение другой. Все вспомогательные и автоматически достигаемые цели исключаются из списка, получая набор S = {S₁, S₂,  … , S_n} независивисимых и слабозависимых целей, для которых рассматривают возможные стратегии их достижения:

С = {C₁, C₂, … , C_m}.

Далее определяют значимость каждой цели  k_j , j{1,…,n} и оценивают эффективность i-той стратегии по отношению к достижению j цели a_ij, i{1,…,m}, j{1,…,n}. Произведение эффективности некоторой стратегии относительно определенной цели на значимость этой цели k_ja_ij называют взвешенной эффективностью i-той стратегии по k  j-той цели. Сумму взвешенных эффективностей данной стратегии называют её общей эффективностью

F_i = k_ja_ij.

Эта величина и выбирается в качестве аддитивного критерия для сравнения стратегии поведения системы.

Методы системной разработки

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

Метод единичной нити

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

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

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

 

Пример. Требуется соединить 3, 4, 5, 8 и 9 объекта 4-мя прямыми, соблюдая следующие условия:

 

¾     нельзя отрывать карандаш от бумаги,

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

                             

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                          

 

Пример психологической инерции

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

Преодолеть психологическую инверсию можно следующим методом:

¾     инверсия – изменение точки зрения, способа использования на прямо  противоположное

¾     эмпатия – отождествление личности одного человека с личностью другого

¾     аналогия – поиск аналогичных ситуаций в весьма далеких областях от исследования

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

Метод большой нагрузки

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

Метод состязательных ситуаций

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

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

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

Обратные задачи – это как раз те оптимизационные задачи, т.е задачи максимизации/минимизации показателя эффективности, которые мы уже упоминали.

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

Введем некоторые необходимые нам в дальнейшем обозначения. Обозначим через X  = {x} – множество допустимых решений, т.е. множество решений, элементы которых удовлетворяют наложенной системе ограничений. Тогда произвольное решение будем обозначать через x. Важно отметить, что x может быть как скалярной, так и векторной величиной, т.е. в общем случае будем рассматривать x как кортеж элементов решения.  Целевую функцию (критерий эффективности) будем обозначать буквой F.

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

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

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

¾     Заранее известные параметры – условия выполнения операции. Обозначим их символом b.

¾     Элементы решения, образующие собой вектор решения x.

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

                                                              F = F(x,b)                                                          (1)

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

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

Пример 1.  (Задача формирования пищевого набора).

Пусть имеется четыре вида продуктов: P_i, где i={1,2,3,4}, из которых нужно составить пищевой набор. При этом требуется, чтобы составляемые пищевые наборы удовлетворяли бы следующим требованиям:

1.      в пищевой набор должны входить все виды продуктов;

2.      содержание белков, жиров и углеводов в пищевом наборе должно быть не менее b₁, b₂ и b₃ соответственно;

3.      стоимость формируемого набора должна быть не больше фиксированной заранее известной величины с_;

4.      вес пищевого набора не должен превышать известную величину p;

5.      сформированный пищевой набор должен иметь минимально возможный при заданных ограничениях объем;

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

На основании исходных данных задачи разработаем ее математическую модель. Обозначим через x_i – количество единиц продукта P_i в пищевом наборе (i = 1…4). Тогда вектор x = (x₁, x₂, x₃, x₄) полностью будет определять свойства любого пищевого набора.

Внимательно просмотрев исходные требования (1) – (6), предъявляемые к пищевому набору, видно, что пункты (1) – (4) формируют систему ограничений, накладываемую на множество решений Х, а (5) – (6) – множество критериев эффективности.

Пусть единица продукта P_i содержит a_i1 грамм белков, a_i2 грамм жиров и a_i3 грамм углеводов, стоит c_i рублей и весит p_i грамм. Тогда систему ограничений (1) – (4) с учетом введенных обозначений можно записать следующим образом:

                                                                                               (2)

Решением данной системы уравнений будут четырехмерные векторы x = (x₁, x₂, x₃, x₄), образующие множество допустимых решений X.

Критерии эффективности (требования (5) и (6)) будут выглядеть следующим образом:

                                     ,                                 (3)

где v_i – объем единицы продукта P_i, а q_i – калорийность единицы продукта P_i.

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

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

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

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

Пример 2. (Задача формирования пищевого набора – смена информационного состояния ЛПР).

Пусть имеется четыре вида продуктов: P_i, где i={1,2,3,4}, из которых нужно составить пищевой набор. При этом требуется, чтобы составляемые пищевые наборы удовлетворяли бы следующим требованиям:

1.       в пищевой набор должны входить все виды продуктов;

2.       содержание белков, жиров и углеводов в пищевом наборе должно быть не менее b₁, b₂ и b₃ соответственно;

3.       формируемый набор должен иметь минимально возможную при заданных ограничениях стоимость_;

4.       вес пищевого набора не должен превышать известную величину p;

5.       объем формируемого пищевого набора не должен превышать величину v;

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

В этом случае пункты (1), (2), (4), (5), (6) формируют систему ограничений, накладываемую на множество решений Х, а (3) – критерий эффективности.

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

                                                                                               (4)

Решением данной системы уравнений будут четырехмерные векторы x = (x₁, x₂, x₃, x₄), образующие множество допустимых решений X.

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

                                                                                                             (5)

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

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

1.       математическая модель должна как можно точнее отражать изучаемые реальные явления;

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

Ввиду очевидной важности такого фактора как информационное состояние ЛПР, все задачи ИСО на основе этого фактора можно разделить на две группы:

¾     Статические задачи ИСО. К этому класс задач мы будем относить задачи принятия решения при постоянном и заранее известном информационном состоянии ЛПР. В этой ситуации вся процедура принятия решения в идеале может быть реализована за один шаг. К этому классу относится большинство задач, которые мы будем рассматривать. Очевидно, что только что рассмотренные примеры 1.1 и 1.2, поясняющие важность информационного состояния, относятся именно к этой группе.

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

Помимо динамики информационного состояния ЛПР важную роль играет и сама «структура» информационного состояния ЛПР. С этой точки зрения задачи ИСО можно классифицировать следующим образом:

¾     Детерминированные задачи. Под детерминированными задачами понимаются задачи, в которых информационное состояние ЛПР соответствует «физическому» состоянию объекта исследований.

¾     Стохастические задачи. В этих задачах информационное состояние ЛПР соответствует множеству «физических» состояний объекта исследований, в условиях определенности. Т.е. в условиях, при которых известны априорные вероятности пребывания объекта в каждом из своих состояний.

¾     Задачи в условиях неопределенности. В этих задачах информационное состояние ЛПР также соответствует множеству «физических» состояний объекта исследований, но в условиях неопределенности. Т.е. в условиях, при которых не известны априорные вероятности пребывания объекта в каждом из своих состояний. Данные задачи являются предметом исследований теории игр.

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

Классификация задач ИСО по виду критерия оптимизации:

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

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

Наиболее распространенным частным случаем задач математического программирования являются задачи линейного программирования. В задачах линейного программирования множество допустимых решений G является подмножеством Âⁿ, где Â - множество действительных чисел, и удовлетворяет системе линейных неравенств W:

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

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

Если задача линейного программирования имеет конечное множество G, то такую задачу принято называть задачей дискретного программирования. Если множество G является подмножеством Zⁿ – целочисленное программирования. В случае же, когда решение может принимать всего два значения ноль и единичку – булево программирование.

Построение линейных оптимизационных моделей

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

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

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

Пример 1. Задача о планировании производства.

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

Предположим, что рассматриваемое предприятие производит товары n видов: T₁, T₂, …, T_n . По каждому виду товара j количество произведенных единиц ограничивается спросом: рынок не может поглотить более k_j единиц товара T_j. В идеале, если позволят имеющиеся ресурсы необходимо насытить спрос по всем товарам. В случае нехватки ресурсов, спрос по отдельным или все товарам может оказаться не насыщенным. При производство товаров тратятся какое-то количество ресурсов. Предположим, что в распоряжении предприятия имеется m видов ресурсов R₁, R₂, …, R_m (сырье, рабочая сила, оборудование и т.д.), в количествах соответственно b₁, b₂, …, b_m единиц.

Для производства одной единицы товара T_j необходимо a_ij единиц ресурса R_i. При этом каждая единица ресурса R_i стоит d_i рублей. Каждая единица товара T_j при реализации приносит доход в размере c_j.

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

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

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

¾     Делимость. Для каждого производственно-технологического процесса суммарное количество каждого из потребляемых ресурсов и соответствующая прибыль строго пропорциональны объему выпускаемой продукции (т.е. в расчете на единицу времени пропорциональны соответствующей производственной мощности, или, как часто говорят, уровню производственной активности). Иначе говоря, все показатели производственно-технологического процесса могут быть увеличены ил уменьшены при сохранении их взаимной пропорциональности. Так, например, если увеличить вдвое все потребляемые ресурсы, то объем выпускаемой продукции и прибыль также возрастут вдвое. Условие делимости предполагает также, что все производственно-экономические показатели могут быть могут принимать не только целочисленные, но и дробные значения.

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

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

Обозначим через x₁, x₂, …, x_n соответственно количество товаров T₁, T₂, …, T_n , которые необходимо запланировать к производству. Запишем задачу в форме задачи линейного программирования:

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

                                            x_j  k_j         :  j {1, …, n}.                                        (1)

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

                                      a_ij x_j  b_i          :  i {1, …, m}.                                 (2)

При производстве каждой единицы товара расходуется некоторое количество ресурсов (в общем случае при производстве каждого товара используются ресурсы всех типов), имеющих заданную стоимость. Исходя из этого себестоимость S_j товара T_j  (j {1…n}) может быть рассчитана следующим образом:

S_j = a_ijd_j          j:  j {1…n}.

Тогда чистая прибыль q_j, получаемая от реализации одной единицы товара T_j равна разнице между ее продажной ценой c_i и себестоимостью s_j, т.е. справедливо следующее равенство:

q_j = с_j – S_j        j:  j{1…n}.

Общая прибыль от реализации всех товаров (искомая целевая функция) примет вид:

                                                           L =  q_jx_j.                                                       (3)

Таким образом, задача сводиться к следующему:

Выбрать такой вектор x = (x₁, …, x_n), который бы удовлетворял условиям (1) и (2), и максимизировал целевую функцию (3). Вообще говоря, такой вектор решения не обязательно является единственно возможным. Могут существовать альтернативные оптимальные решения или, как мы их будем называть в дальнейшем, альтернативы.

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

Пример 2. Задача о загрузке станков.

Ткацкая фабрика располагает двумя видами станков, из них N₁ станками типа 1 и N₂ станками типа 2. Станки могут производить четыре вида тканей: T₁, T₂, T₃, T₄, но с разной производительностью. Известно, что станок типа i производит в месяц a_ij метров ткани T_j. Каждый метр ткани T_j приносит фабрике доход с_j.      Фабрике предписан план, согласно которому она обязана произвести за месяц не менее b_j метров ткани T_j. Необходимо так распределить загрузку станков производством тканей различного вида, чтобы план был выполнен, и при этом месячная прибыль была максимальной.

Данная задача очень похожа на предыдущий пример и, в подтверждение принципа психологической инерции, о котором говорилось ранее, хочется обозначить через x₁, x₂, x₃, x₄ производимое количество тканей T₁, T₂, T₃, T₄ соответственно и максимизировать суммарный доход c₁*x₁ + c₂*x₂ + c₃*x₃ + c₄*x₄. Однако это будет в корне не верно. На самом же деле элементами решения в данной задаче не количества тканей каждого вида, а количества станков типа 1 и 2, занятых производством тканей каждого вида.

В этой задаче элементы решения мы будем обозначать через x_ij, где i определяет тип станка, а j вид ткани производимой на станках данного типа (i{1,2}, j{1,..,4}). Таким образом, всего у нас будет восемь элементов решения, которые надо выбрать так, чтобы месячная прибыль была максимальной.

Запишем условия-ограничения, наложенные на элементы решения x_ij. Прежде всего, необходимо обеспечить выполнение директивного плана. Это даст нам систему из четырех неравенств.

                                           a_ijx_ij  b_j     j: j  {1,..,4}.                                       (1)

 

Осталось записать ограничения, связанные с наличием оборудования и его загрузкой. Суммарное количество станков типа 1, занятых изготовлением всех тканей, должно быть равно N₁, типа 2 – N₂. Отсюда еще два условия – два равенства:

                                             x_ij  N_i      i: i  {1,2}.                                          (2)

Теперь запишем суммарный доход от производства всех видов тканей на всех имеющихся в распоряжении станках. Суммарное количество ткани T₁, произведенное всеми станками будет равно a₁₁*x₁₁ + a₂₁*x₂₁ и принесет прибыль с₁(a₁₁*x₁₁ + a₂₁*x₂₁). Проводя аналогичные рассуждения, найдем суммарный доход фабрики:

L = с₁(a₁₁*x₁₁ + a₂₁*x₂₁) + с₂(a₁₂*x₁₂ + a₂₂*x₂₂) + с₃(a₁₃*x₁₃ + a₂₃*x₂₃) + +с₄(a₁₄*x₁₄ + a₂₄*x₂₄)

или, что короче:

                                                                                                           (3)

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

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

Пример 3. Транспортная задача.

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

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

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

Предположим, что имеется n пунктов потребления (например, промышленных предприятия) П_j, j{1..n}, требующих снабжения определенным видом сырья. Потребности в сырье каждого предприятия П_j равны соответственно b_j единиц, j{1..n}. Кроме того, имеется m складов С_i , i{1..m}, на которых хранится требуемое предприятиям сырье. На каждом складе С_i  имеется запас товара в количестве a_i, i{1..m}. Склады удалены от предприятий на некоторые расстояния и связаны с ними некоторыми путями сообщений с различными тарифами. Единица сырья, получаемая предприятием П_j со склада C_i с учетом известных тарифов на перевозки, обходится  в c_ij рублей. Для простоты предположим, что все заявки выполнимы, т.е. сумма всех заявок не превосходит сумму всех имеющихся запасов:

.

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

Сформулируем задачу линейного программирования.       Обозначим x_ij количество единиц сырья, направляемого со склада С_i  предприятию П_j. Всего план перевозок будет состоять из m*n элементов решения: {x₁₁, x₁₂, …, x_1n, x₂₁, x₂₂, …, x_2n, …, x_m1, x_m2, …, x_mn}.

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

                                                  {1..m}.                                            (1)

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

                                                  {1..n}.                                          (2)

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

                                                         .                                                     (3)

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

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

,

Это происходит в ситуации, когда сумма всех заявок равняется сумме всех запасов.

                                                                                   

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

Предприятия-потребители и склады можно представить в виде некоторой совокупности точек на плоскости, или, если обратиться к терминологии теории графов, в виде некоторого множества узлов. Тогда каждая управляемая переменная x_ij соответствует потоку вдоль дуги, соединяющей узел i и узел j, а c_ij – затраты на прохождение единицы данного потока. Полные затраты на поток между узлами i и j будет равен произведению стоимости единицы потока на объем потока, т.е. c_ij*x_ij. Для того, чтобы сделать сетевую модель более определенной необходимо в соответствующих узлах указать количество имеющегося на складе сырья, если узел представляет собой склад, и потребности в сырье, если узел представляет собой предприятие-потребителя. В литературе по организационному управлению такая задача называется транспортная задача Хитчкока – Купманса. (Hitchcock F.L.–1941— Koopmans T.C. – 1947). Сеть для рассматриваемого примера приведена на рисунке ниже.

 

 

 

 

                        Склады                                                            Потребители

                                                                                            

                                                                                                    

     

 

                                           

                                                                                                                  

                     

                                            

           

 

 

 

 

                                      

Пример 4.   Задача о кратчайшем маршруте.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Сетевая модель для задачи
о кратчайшем маршруте

 

Отметим, что существует путь из каждого узла {1, 2, 3, 4} в любой другой узел j : j Î {2,3,4,5} при условии, что j > i. Этот путь может проходить либо по одной дуге, непосредственно со­единяющей рассматривае­мые узлы, либо по ряду дуг через промежуточные узлы, если j – i > 1. Так, например, путь от узла 1 к узлу 5 может быть прямым (вдоль дуги (1, 5)), вдоль (1, 2), (2, 5) или вдоль (1, 3), (3, 4), (4, 5). Аналогично можно указать возможные пути и для любой другой пары узлов.                                 

Допустим, что с перемещением вдоль ка­ждой дуги (i, j) связаны со­ответственно затраты . Между значениями c_ij не устанавливается никакой определенной зависимости, а графическое изображение модели сделано без учета длин дуг (i, j). Как правило, в подобных задачах c_ij ³ 0, однако в данном случае нет надобности в подобном предположении. Кроме того, необходимо отметить, что в большинстве случаев .

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

Пусть  - затраты, связанные с использованием наиболее дешевого маршрута от узла i до узла 5, где i {1,2,3,4}. Можно определить y, подсчитав затраты для прямого маршрута от узла i до узла j ( j > i ) и прибавить к ним затраты для оптимального маршрута от узла j до узла 5. Наименьшее из всех производимых при этом затрат определяет значение y.

Математически это можно сформулировать следующим образом:

min (  ),      {1,2,3,4}, .

Таким образом, затраты в случае выбора наиболее дешевого маршрута от узла 1 до узла 5 можно определить, если известны затраты, связанные с использованием наиболее дешевого маршрута от узла 2 до узла 5. В свою очередь самый экономичный маршрут от узла 2 до 5 можно определить, если известен оптимальный маршрут от 3 до 5 и т.д. Таким образом, в этом случае задача сводится к сравнению затрат, связанных с использованием прямого маршрута от узла-истока 1 до узла-стока 5, с затратами при использовании маршрута от узла 1 через каждый из промежуточных маршрутов и выбору наилучшего пути от узла 1 до узла 5.

         

 

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

max

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

                                           

            

                                                          

 

 

                                  

 

 

 

 

 

Эквивалентность этих записей доказывается следующим образом. По определению не может превышать значения  (i Î {1, 2, 3, 4}, j Î {2, 3, 4, 5}, j > i), но равняется, по крайней мере, одному их этих значений, что обеспечивает требование максимизации .

Пример 5.   Задача о замене оборудования.

Транспортное агентство разрабатывает план аренды транспортного оборудования на период n лет. Агентство может выполнить обязательства по перевозке грузов, взяв в аренду новую транспортную единицу в начале первого года и эксплуатировать ее до начала j года (j £ n+1). Если j £ n+1, то агентство заменяет эту единицу в начале года j и эксплуатирует новую до начала года k (k  n + 1) и т.д. Величина затрат включает арендную плату плюс ожидаемые расходы на ремонт и обслуживание оборудования. Заметим, что в сети, которая ничем не отличается от сети предыдущей задачи, отсутствуют циклы. Такая сеть называется ациклической.

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

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

Сетевая модель для задачи
 о замене оборудования

 

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

Пример 6. Задача о ранце.

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

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

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

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

                                                            Q.                                                        (1)

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

                                                            .                                                        (2)

Следовательно, необходимо максимизировать (2) при ограничении (1).

Пример 7.  Задача о назначении.

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

Так как по условию задачи количество работ в точности равно количеству исполнителей, а один исполнитель не может выполнить несколько работ, то каким бы ни было решение этой задачи, оно будет содержать в себе таблицу назначений работ исполнителям. Т.е. n пар вида <номер исполнителя, номер работы>. Очевидно, что в этой ситуации удобно представить задачу в табличной форме, где столбцы будут означать распределение некоторой работы по исполнителям, а строки – назначение исполнителю некоторой работы. Тогда удобно ввести следующие управляемые переменные:

 

                 1, если работа i выполнена исполнителем j,

                 0, в остальных случаях.

 

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

                                                    {1..n}.                                             (1)

Каждый исполнитель j должен выполнять только одну работу (это означает, что в каждой строке таблицы будет только одна единица):

                                                   {1..n}.                                            (2)

Тогда затраты на весь объем работ (наша целевая функция) составят:

                                                         .                                                     (3)

Нетрудно видеть что, модель (1), (2), (3) является частным случаем классической транспортной задачи, в которой m = n и .

Пример 8. Задача о распределении ресурсов.

Этот пример иллюстрирует универсальность задачи о кратчайшем пути. Как и в примере 2.5, сеть должна быть ациклической.

Предположим, что некоторой строительной компании необходимо разработать план капиталовложений на текущий год. Общий капитал, которым она располагает и который нужно распределить по различным объектам составляет С единиц. Финансовый отдел предложил на рассмотрение президента компании n возможных объектов капиталовложений. При этом финансовым отделом был произведен ряд расчетов, позволяющих точно сказать, что если в i-ый объект вложить k ресурсов, то прибыль будет оцениваться величиной . Будем считать, что при любых условиях справедливо неравенство . Компания стремится так распределить капиталовложения по объектам, чтобы максимизировать общую прибыль. Пусть капиталовложения можно распределять в объемах, кратных одной единице.

Сеть, описывающая рассматриваемый пример строится следующим образом. Для каждого объекта капиталовложений ввозится столбец узлов. В обозначении узла (i, C_i) символ i представляет собой номер объекта, а величина C_i определяет объем капитала, который можно вложить в объект i при условии принятия решений по ранее рассмотренным объектам. Каждая дуга, исходящая из узла (i, C_i) соответствует конкретному принятому решению по объекту i. Дуга, исходящая из узла (i, C_i), должна быть помечена числом , если принято решение в i-ый объект вложить k ресурсов, и никак не помечена, если принято решение не вкладывать ресурсы в объект i (т.е. k = 0).

Предположим, что размер капиталовложений, имеющихся в распоряжении компании, составляет три единицы, т.е. C = 3, а количество объектов капиталовложений – тоже три, т.е. n = 3.

    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                     

                                            

 

 

 

 

 

 

Сетевая модель для задачи о распределении ресурсов

Таким образом, любой допустимый вариант распределения капиталовложений можно представить в виде проходящего через всю сеть маршрута (исток – (1,3), … , сток – (4,0)) и, следовательно, задача состоит в отыскании пути максимальной длины.

Примем, что - объем капитала, вложенного в объект i, и определим следующую неубывающую функцию:                                

 

 

                              

 

 

Тогда математическая модель задачи может быть записана в виде:

max ,

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

.

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

Нетрудно заметить, что задача о ранце, в сущности, в некотором смысле ничем не отличается от задачи о распределении ресурсов. Процесс загрузки ранца можно представить себе состоящим из n шагов, на каждом из которых нам необходимо ответить на вопрос: брать данный предмет в ранец или не брать? Применяя переменные, описанные при построении математической модели задачи о назначении, положим , если мы выбираем i–ый предмет, и  в противном случае. Таким образом, в данном случае решение задачи – набор значений x_i (i = 1…n) – определяет принадлежность предметов выбранному набору, в то время как в задаче о назначении, решение определяло принадлежность объекта выбранному списку объектов капиталовложений. В сущности, это одно и тоже.

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

Давайте рассмотрим простой пример, иллюстрирующий только что описанный подход:

 

 

 

 

 

 

 

 

 

 

 

 

        

         Сетевая модель для задачи о ранце

На рисунке изображена сеть для следующего примера: Q = 6

 

Презм.	П	П	П
Вес	1	2	4
Ст.	1	4	2

 

 

В построенной ациклической сети можно выделить 4 маршрута, из которых только один (x₁ = 0, x₂ = 1, x₃ = 1) является искомым: L = 6.

 

 

Пример 9.   Задача о максимальном потоке в сети с ограниченными пропускными способностями.

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

max F,

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

F,     k = 0;

,     k = 1,2,…,(p-1);

F,      k = p;

0 ,        .

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

Для этого примера max F = 3.

Подробнее эта задача и методы ее решения будут рассмотрены позже.

Геометрическая интерпретация ЗЛП

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

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

.

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

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

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

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

Кроме того, известно, что реализация каждого изделия А приносит прибыль 2 единицы, а реализация каждого изделия В – 3 единицы.

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

Математическая модель задачи может быть построена следующим образом:

Обозначим x₁ и x₂  количество заложенных в производственный план изделий видов А и В соответственно. Обозначим буквой F получаемую при реализации производственного плана прибыль. Тогда с учетом этих обозначений имеем:

 

                          или        

Оп.1      +                        +     

Оп.2       +                        +         8

Оп.3                                                         6

Оп.4                                                        8

 

            max F =                            max F =

 

 

Строго говоря, не переменные  и  нужно было бы наложить еще требование целочисленности.

Дадим геометрическую интерпретацию данной задачи линейного программирования в пространстве решений  и . Заметим, что система ограничений изображена графически (прямые линии) как система уравнений, полученная путем замены фигурирующих в ней неравенств на равенства. Отсекаемая этими прямыми область пространства решений вместе с граничными точками представляет собой область допустимых решений (сокращенно ОДР) данной задачи линейного программирования. Поскольку ни одна из управляемых переменных не может принимать отрицательных значений, область допустимых решений x₁ и x₂, ограничена и осями координат, образуя, таким образом, выпуклый многоугольник. Выпуклость многоугольника означает, что любой отрезок, соединяющий две произвольным образом выбранные точки данного множества, лежит внутри него или проходит его границы, т.е. принадлежит ему. Вершины О, C, D, E и F называются экстремальными точками – они не могут принадлежать внутренней части ни одного из отрезков, принадлежащих данному выпуклому многоугольнику.

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

Пример геометрической интерпритации ЗЛП

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

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

,  ,  F = 2D.         

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

 4 +  2×4  = 12

4 +     4  =   8

4            <   6

          4  <   8

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

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

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

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

max  F=

при наличии следующей системы ограничений W:

W: {}

и дополнительных условий неотрицательности значений управляемых переменных:

При n управляемых переменных необходимо рассматривать n-мерное евклидово пространство, каждая точка которого будет задаваться вектором размерности n, например,`x = (x₁, x₂, x₃, …, x_n-1, x_n). Из примененной системы ограничений и условий видно, что область допустимых решений будет представлять собой некоторую замкнутую область n-мерного пространства решений.

Каждому уравнению вида

будет соответствовать гиперплоскость, делящая рассматриваемое n-мерное пространство на два подпространства. В соответствии со знаком (£) использованного для разбиения неравенства выбирают то или иное из полученных подпространств. Далее переходят к рассмотрению выделенного подпространства. Пересечение m+n гиперплоскостей (m ограничений + n условий неотрицательности) и даст область допустимых решений. Если полученное множество является не пустым, то оно будет представлять собой выпуклый многогранник. Целевая функция также может быть представлена в виде гиперплоскости в пространстве решений.

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

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

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

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

 

  

                                                                                          (1)

 

Преобразованная из системы неравенств W система линейных уравнений

                                                   ,                                                (2)

определяющая область допустимых решений, содержит число уравнений, равное рангу ее матрицы, т.е. является базисной. Таким образом, имеем m £ n + m. Так как при m = n + m система (2) будет иметь единственное решение, а множество допустимых решений не сможет содержать более одного элемента, то в общем случае можно полагать, что m  < n + m.

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

в уравнение, при замене знака неравенства на знак равенства к левой его части полученного уравнения необходимо добавить вновь введенную переменную x_n+i:

Преобразовав все m неравенств в уравнения, и внося новые переменные под знак суммы, перепишем полученную систему уравнений в виде (2):

,

где для любого j > n, коэффициент a_ij равен (до преобразования системы неравенств в системe уравнений у нас было m*n коэффициентовa_ij, а после преобразования – (n+m)*m):

В системе уравнений (2), приведение к которой системы неравенств W из (1) было только что описано, содержит m базисных переменных x_n+1, …, x_n+m и n свободных – x₁, …, x_n. Вводя матричные обозначения

,  ,  ,  ,  

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

                                                                                                           (3)

Оставшиеся условия неотрицательности будут дополнены условиями неотрицательности, наложенными на новые переменные:

                                                                                                        (4)

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

                                                                                                              (5)

Тогда задачу максимизации (5) при ограничивающих условиях (2) и требованиях неотрицательности (4) будем называть основной задачи линейного программирования.

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

Пример 1: Базис и базисные переменные математической модели.

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

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

Решение:

Вводя следующие обозначения:

 и

получаем:

Из уравнения (3) выразим столбец базисных переменных:

                                                                                                      (6)

Таким образом, для любого , вектор  является решением уравнения (3). Если при этом выполняется то условие, что X ³ N₀, где N₀ – нуль вектор в пространстве решений размерности n + m, то решение X является допустимым решением. Возвращаясь к полученному выражению (6), скажем, что в случае равенства нуль вектору вектора свободных переменных, решение уравнения (3) примет вид:

                                                                                                           (7)

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

Очевидно, что выбор правило, введенное нами для выбора базисных столбцов не является единственно истинным. Строго говоря, в качестве базисных переменных можно было выбрать различные m из n + m имеющихся управляемых переменных математической модели, и взять оставшиеся n в качестве свободных. Введение какого-либо правила назначения базисных переменных обусловлено необходимость строгой формализации процесса решения задачи. При решении практических задач можно пользоваться этим или любым иным правилом, помня, что выбор базисного решения не является однозначным. Рассмотрим пример.

Пример 2. Выбор базисных переменных.

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

x₁ + 2*x₂ £ 8

x₁ + x₂ £ 6

Для того, чтобы перейти к форме основной задачи линейного программирования необходимо ввести m (в данном случае m = 2) дополнительных базисных переменных: x₃ и x₄. В данном примере нашей задачей является рассмотрение только вопросов, связанных с выбором базисных переменных, поэтому мы здесь вообще никак не затронем рассмотрение целевой функции. Кроме того, в процессе всех преобразований мы не будем отдельно останавливаться на определении требований неотрицательности управляемых переменных, полагая, что на все исходные управляемы переменные и на все вводимые нами дополнительные переменные это требование распространяется автоматически. Перепишем заданное множество ограничений с учетом новых обозначений:

x₁ + 2*x₂ + x₃ = 8

x₁ + x₂ + x₄ = 6

Тогда матрица А, равная конкатенации А₁ и А₂ может быть записана в следующем виде:

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

B₁ = {1, 2}, B₂ = {1, 3}, B₃ = {1, 4}, B₄ = {2, 3},
B₅ = {2, 4}, B₆ = {3, 4}

Им будут соответствовать следующие матрицы:

, , ,
, ,

 

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

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

X₂ = (6, 0, 2, 0)^T, X₃ = (8, 0, 0, -2)^T, X₄ = (0, 6, -4, 0)^T,
X₅ = (0, 4, 0, 2)^T, X₆ = (0, 0, 8, 6)^T,

В соответствии с определением допустимых базисных решений, допустимыми в данном примере будут следующие базисные решения: X₁, X₂, X₅ и X₆.

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

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

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

                                                           ,                                                        (7)

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

                                                                                           (8)

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

                                     ,                                  (9)

а система линейных ограничений:

                                                                               (10)

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

                                                                                                                           (11)

Проанализировав систему преобразованных неравенств (10) с учетом найденных уже значений свободных переменных (11), делаем вывод о том, что

                                                                                                                         (12)

 

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

Пример 3. Определение решения по внешнему виду задачи.

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

   Очевидно, что в данной задачи базисом является: , следовательно,

.

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

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

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

.

 

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

 

 

.

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

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

Например, если , то e=2.

Таким образом e-столбец будем выбирать по следующему формальному правилу:

.

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

В связи с этим целесообразно дополнительно исследовать следующее отношение:

Выберем строку, которой соответствует наименьшее положительное значение . Выбранную по этому правилу строку будем называть s-строкой, т.е.:

.

Возвращаясь к нашему примеру, определяем базис: . Тогда. Кроме того, пусть , тогда s=4. Элемент , стоящий на пересечении e-столбца и s-строки, будем называть  ведущим элементом.

Чтобы поменять местами e-столбец и s-строку, почленно разделим все элементы s-строки на ведущий элемент. В результате данной операции мы получим е-строку в новой  таблице:

,

где индексы k и k+1 обозначат порядковый номер соответствующих итераций.

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

.

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

 

 

 

 

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

1.       Вычислить допустимое решение R в соответствии со следующим правилом:

                                         .                                    (13)

2.       Проанализировать значения коэффициентов при свободных переменных:

Если окажется, что все , то получено единственное оптимальное решение R:

.

Если окажется, что все , то найдено одно из эквивалентных решений R:

.

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

                                    .                              (14)

3.       Произвести замену е-столбца и s-строки, т.е. включить в базис, одновременно исключив из него :

1.1.     На месте ведущего элемента  необходимо записать его обратную величину:

                                                           .                                                      (15)

2.2.     Строку, где находится ведущий элемент, требуется разделить на ведущий элемент:

                                                           .                                                     (16)

3.3.     Столбец, где находится ведущий элемент, делят на ведущий элемент с обратным знаком:

                                                         .                                                    (17)

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

                                                    .                                               (18)

4.       Перейти к пункту 1 алгоритма.

 

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

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

Решить данную задачу с помощью симплекс-метода, если целевая функция задана следующим соотношением:

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

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

1 итерация (k=1):

В соответствии с выражением (13) вычислим текущее допустимое решение:

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

В соответствии с формулой (14) алгоритма найдем е-строку и s-столбец:

e-строке будет соответствовать максимальный положительный коэффициент при свободной переменной. Таким образом, определяем:

.

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

Тогда, очевидно (см. соотношение (14)), что на данной итерации индекс s строки равен 3, т.е.:

.

В соответствии с формулами (15), (16), (17) и (18) произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

2 итерация (k=2):

В соответствии с выражением (13) вычислим текущее допустимое решение:

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

В соответствии с формулой (14) алгоритма найдем е-строку и s-столбец:

.

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

 

 

Тогда, очевидно (см. соотношение (14)), что на данной итерации индекс s строки равен 3, т.е.:

.

В соответствии с формулами (15), (16), (17) и (18) произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

3 итерация (k=3):

В соответствии с выражением (13) вычислим текущее допустимое решение:

.

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

 

Пример 5. Задача о планировании производства.

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

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

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

, .

Решение:

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

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

 

Геометрическая интерпретация задачи о планировании производства

Решим теперь данную задачу симплекс-методом.

Прежде всего, как и в предыдущем примере, на основании исходных данных построим симплекс-таблицу:

1 итерация (k=1):

В соответствии с формулой (13) вычислим текущее допустимое решение:

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

В соответствии с формулой (14) алгоритма симплекс-метода найдем е-строку и s-столбец:

e-строке будет соответствовать максимальный положительный коэффициент при свободной переменной. Таким образом, определяем:

.

Для определения s-строки необходимо дополнительно рассчитать столбец значений g. Результаты расчетов представлены ниже:

Тогда в соответствии с формулой (14) делаем вывод о том, что на данной итерации индекс s строки равен 4, т.е.:

.

Опираясь на соотношения (15), (16), (17) и (18), произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

2 итерация (k=2):

В соответствии с формулой (13) вычислим текущее допустимое решение:

.

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

В соответствии с формулой (14) алгоритма найдем е-строку и s-столбец:

.

Для определения s-строки необходимо дополнительно рассчитать столбец значений g. Результаты расчетов представлены ниже:

 

 

Из приведенной таблицы видно (см. соотношение (14)), что на данной итерации индекс s строки равен 5, т.е.:

.

В соответствии с формулами (15), (16), (17) и (18) произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

3 итерация (k=3):

В соответствии с формулой (13) вычислим текущее допустимое решение:

.

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

 

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

 

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

                                                        (19)

Обозначим только что рассмотренное условие A, а эквивалентное преобразование (19) оператором М.

 

B.      Если в некоторой задаче линейного программирования в системе линейных ограничений существует хотя бы одно ограничение следующего вида:

                                  ,                                (20)

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

                               ,                             (21)

Обозначим только что рассмотренное условие B, а эквивалентное преобразование (20) ® (21) оператором N.

 

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

                                       (22)

Обозначим только что рассмотренное условие C, а эквивалентное преобразование, заданное соотношением (22) оператором P.

 

D.     Если в некоторой задаче линейного программирования существует отрицательный свободный член выполнить оператор К (осуществить поиск опорного решения), иначе выполнить оператор L (воспользоваться для решения симплекс-методом).

Обозначим только что рассмотренное условие D.

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

 

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

.

2.         Определить s-строку в соответствии с правилом:

.

3.         Произвести замену e-столбца и s-строки. Здесь замена производится аналогично замене в алгоритме симплекс-метода.

4.         Проверить выполнение условия D.

                                            

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

 

Пример 6. Задача линейного программирования в произвольной форме.

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

Решить данную задачу симплекс-методом.

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

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

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

По условию задачи все неравенства системы линейных ограничений содержат знаки «больше или равно». Тогда, основываясь на результатах проверки условия B, применим к каждому неравенству данной системы ограничений оператор N. Новая симплекс таблица примет вид:

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

1 итерация (k=1):

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

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

.

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

В соответствии с пунктом 2 алгоритма поиска опорного решения на данной итерации индекс s строки равен 5, т.е.:

.

В соответствии с формулами (15), (16), (17) и (18) алгоритма симплекс-метода произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

2 итерация (k=2):

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

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

^.

Для определения s-строки необходимо дополнительно рассчитать столбец g. Результаты расчетов представлены ниже:

В соответствии с пунктом 2 алгоритма поиска опорного решения на данной итерации индекс s строки равен 4, т.е.:

.

В соответствии с формулами (15), (16), (17) и (18) алгоритма симплекс-метода произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

3 итерация (k=3):

В соответствии с выражением (13) вычислим текущее допустимое решение:

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

 

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

 

Алгоритм решения произвольной задачи линейного программирования

Анализ на чувствительность

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

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

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

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

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

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

,

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

1.       максимизировать целевую функцию:

                                                         ,                                                      (1)

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

                                                                                           (2)

2.       минимизировать целевую функцию:

                                                          ,                                                      (3)

при заданной системе ограничений:

                                                                                          (4)

Назовем первую задачу (соотношения (1) и (2)) прямой задачей линейного программирования, а вторую (соотношения (3) и (4)) – двойственной задачей линейного программирования по отношению к первой.

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

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

 

Максимизировать целевую функцию:

при условии:

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

 

Минимизировать целевую функцию:

при условии:

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

 

Введя обозначения:

                                                                     (5)

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

 

Прямая задача:

                                                                                                                    (6)

                                            

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

                                                                                                                   (7)

Следует отметить, что задача линейного программирования, двойственная к задаче (7), совпадает с исходной задачей линейного программирования (6).

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

Имеет место следующая теорема:

 

Теорема двойственности.

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

1.       существует оптимальное решение прямой задачи ;

2.       существует оптимальное решение двойственной задачи ;

3.       имеет место следующее соотношение:

                                                                                                            (8)

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

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

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

                                                                                                (9)

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

                                                                                             (10)

Так как выражения в левых частях неравенств (9) и (10) совпадают, имеет место следующее неравенство:

                                                                                                          (11)

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

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

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

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

 

 

 

 

Теорема о дополнительной нежесткости.

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

                                                                                     (12)

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

Рассмотрим теперь экономическую интерпретацию переменных в задаче линейного программирования, являющейся двойственной по отношению к рассмотренной уже нами задаче распределения ограниченных ресурсов. Будем рассматривать задачу распределения ресурсов как прямую, предполагая, что она записана в виде (1)-(2) или (6) с неотрицательными параметрами, а двойственная ей задача представлена в виде (3)-(4) или (7).

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

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

Дадим теперь экономическую интерпретацию рассмотренной ранее теоремы о дополнительной нежесткости.

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

Если в оптимальном решении i-тый ресурс используется не полностью, то его теневая цена должна быть равна нулю, т.е.:

В заключение скажем, что объем вычислительных затрат, связанных с нахождением оптимального решения любой задачи линейного программирования, определяется в большей степени не числом свободных переменных модели n, а числом линейных ограничений m. А так как любую задачу линейного программирования можно рассматривать в плоскости «прямая-двойственная» и решение любой из этих задач симплекс-методом автоматически приводит к решению другой, то целесообразно решать именно ту задачу, система ограничений которой содержит меньшее число соотношений.