Кутузов А.Л. Математические методы и модели исследования операций. Линейная оптимизация с помощью WinQSB и Excel

Подождите немного. Документ загружается.

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

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

моделирования.

1.7. Человеческий фактор

Очевидно, сами по себе количественные методы (строгая математическая

постановка задачи, получение численных результатов и т. п.) не решают всех

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

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

факторов, не все из которых могут быть учтены при построении соответствующих

математических моделей. Это с одной стороны.

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

по всем параметрам, наталкивается на «человеческий фактор» и в результате не

может быть принято. Рассмотрим пример под названием «Кошмарные

автогонки» [18].

«Два соперника стартуют с разных концов узкой горной дороги» с крутыми обрывами

или отвесными скалами по сторонам. Тот, кто первым достигнет противоположного

конца, получит $1 000 000. Вот гонщики съехались и притормозили. Что им делать

дальше?»

Возможные варианты решения:

Дать одному гонщику задний ход — в этом случае второй получит фору, вполне

достаточную для победы.

Оба гонщика продолжают двигаться вперед — это решение, очевидно, приведет

гибели обоих гонщиков.

Можно договориться гонщикам о дележе выигрыша и закончить гонку вместе в

одном из автомобилей.

Ясно, что из всех вариантов последний вариант решения будет наиболее

приемлемым, однако именно здесь начинает «работать» человеческий фактор. Так,

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

силен, может отказаться от этого варианта

из-за опасения, что от него могут просто

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

скорее всего, пойдут пешком, медленно и с опаской, но, однако, не теряя надежды на

благополучный исход и дележ выигрыша.

1.8. Математические модели операций

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

требуется какая-то математическая модель. При построении модели реальное

явление (в нашем случае — операция) неизбежно упрощается, схематизируется, и

эта схема («макет» явления) описывается с помощью того или другого

математического аппарата. Чем удачнее будет подобрана математическая модель,

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

исследование и полезнее вытекающие из него рекомендации.

Типичная математическая модель исследования операций схематически можно

представить следующим образом:

Максимизация или минимизация целевой

функции

При условии выполнения ограничений

Ст

. 11 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

Общих способов построения математических моделей не существует. В каждом

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

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

определить и влияние каких факторов отразить). Необходимо также в каждом

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

с той точностью, с которой нам нужно знать решение;

с той информацией, которой мы располагаем или можем приобрести.

Если исходные данные, нужные для расчетов, известны неточно, то, очевидно, нет

смысла входить в тонкости, строить очень подробную модель и тратить время (свое и

машинное) на тонкую и точную оптимизацию решения. К сожалению, этим принципом

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

Математическая модель должна отражать важнейшие черты явления, все

существенные факторы, от которых в основном зависит успех операции. Вместе с

тем, модель должна быть по возможности простой, не «засоренной» массой мелких,

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

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

Не берите в качестве модели Вселенной саму Вселенную!!!

Две опасности всегда подстерегают составителя модели: первая — увязнуть в

подробностях («из-за деревьев не увидеть леса») и вторая — слишком огрубить

явление («выплеснуть вместе с водой и ребенка»). Искусство строить

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

постепенно.

Современные менеджеры строят сами математические модели в простых случаях

либо руководят коллективом разработчиков, если модель сложная. Очень важно, что

и в том, и в другом случае сами менеджеры принимают самое активное участие в

построении модели. Все дело в том, что только они понимают все тонкости

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

что — второстепенное, несущественное и может быть отброшено. Действительно,

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

учтены главные свойства моделируемого объекта;

отброшены его второстепенные свойства.

ВНИМАНИЕ

В умении отделить главные свойства моделируемого объекта от второстепенных и состоит искусство

разработчика модели.

Аналитические и имитационные модели

При построении математической модели может быть (в зависимости от вида

операции, задач исследования и точности исходных данных) использован

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

в самых простых случаях явление описывается простыми, алгебраическими

уравнениями;

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

аппарат дифференциальных уравнений (обыкновенных или с частными

производными);

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

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

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

имитационного моделирования.

Ст

. 12 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

В исследовании операций широко применяются как аналитические, так и

имитационные модели. Каждый из этих типов имеет свои преимущества и

недостатки.

налитические модели более грубы, учитывают меньшее число факторов, всегда

требуют каких-то допущений и упрощений. Зато результаты расчета по ним легче

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

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

решений.

Имитационные модели, по сравнению с аналитическими, более точны и подробны,

не требуют столь грубых допущений, позволяют учесть большое (в теории —

неограниченно большое) число факторов. Но и у них — свои недостатки:

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

крайняя трудность поиска оптимальных решений, которые приходится искать «на

ощупь», путем догадок и проб.

Молодые специалисты, чей опыт в исследовании операций мал, имея в

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

исследование с построения имитационной модели, стараясь учесть в ней как можно

больше факторов. Они забывают, что построить модель и произвести по ней

расчеты — это полдела; важнее суметь проанализировать результаты и перевести их

в ранг «рекомендаций».

ВНИМАНИЕ

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

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

общих чертах разобраться в явлении, наметить как бы «контур» основных закономерностей. Любые

уточнения могут быть получены с помощью имитационных моделей.

Глава 2. Линейное программирование

инейное программирование — это метод математического моделирования,

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

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

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

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

отрасли, системе здравоохранения и даже в социальных науках, но особенно широко

оно применяется в экономике.

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

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

На алгоритмах линейного программирования (учитывая их компьютерную

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

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

и стохастическое программирование.

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

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

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

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

прикладных программ, например QSB+ и QS, описанные в учебнике, значительно

облегчают эту вычислительную ношу.

2.1. Пример разработки математической модели

Рассмотрим основные элементы модели линейного программирования на простом

Ст

. 13 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

примере с двумя переменными.

2.1.1. Планирование производства краски

Компания производит краску для внутренних и наружных работ из сырья двух типов:

Ml и М2. Основные данные для задачи представлены в следующей таблице (где

через РС обозначен «Расход сырья в тоннах»):

Из-за отсутствия надлежащего спроса отдел маркетинга компании ограничил

ежедневное производство краски для внутренних работ до 2 т, а также поставил

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

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

внешних работ.

Компания хочет определить оптимальное (наилучшее) соотношение между видами

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

Задача (модель) линейного программирования, как и любая задача исследования

операций, включает три основных элемента:

Переменные, которые следует определить.

Целевая функция, подлежащая оптимизации.

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

Рассмотрим отдельно каждый из этих шагов.

Определение переменных

Определение переменных — первый шаг в создании модели. После определения

переменных построение ограничений и целевой функции обычно уже не вызывает

особых трудностей.

В нашем примере необходимо определить ежедневные объемы производства краски

для внутренних и наружных работ. Обозначим эти объемы как переменные модели:

— ежедневный объем производства краски для наружных работ;

— ежедневный объем производства краски для внутренних работ.

Построение целевой функции

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

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

олжна возрастать при

увеличении ежедневных объемов производства красок. Обозначим эту функцию

через z (она измеряется в тысячах долларов) и положим, что

z = 5x

+ 4x

В соответствии с целями компании получаем задачу:

Максимизировать z = 5x

+ 4x

РС на 1 т краски

для наружных

абот

РС на 1 т краски

для внутренних

абот

Максимально

возможный

ежедневный РС

Сырье M1 6 4 24

Сырье М2 1 2 6

Прибыль (в

$1000) на 1 т

краски

5 4

Ст

. 14 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

ПРИМЕЧАНИЕ

Часто встречается и такая запись требования максимизации целевой функции: z = 5x

+ 4x

→

max.

Поскольку здесь используется стрелка, как и в теории пределов, эту запись часто ошибочно

интерпретируют следующим образом: «Функция z стремится к максимуму». Это неправильно. Нужно

читать эту запись так: «Найти максимум функции z» или «Максимизировать функцию z».

Ограничения

Итак, остался не определенным последний элемент модели — условия

(ограничения). Они должны учитывать ограниченные возможности ежедневного

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

ограничения на сырье можно записать следующим образом: (используемый объем

сырья для производства обоих видов краски)

≤

(максимально возможный ежедневный

расход сырья).

Во-первых

, из таблицы с данными задачи имеем:

используемый объем сырья M1 = 6x

+ 4x

(т),

используемый объем сырья М2 = 1x

+ 2x

(т).

Так как ежедневный расход сырья M1 и М2 ограничен соответственно 24 и 6 тоннами,

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

+ 4x

≤

24 (сырье M1)

+ 2x

≤

6 (сырье М2)

Во-вторых

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

Максимальный ежедневный объем производства краски для внутренних работ не

должен превышать 2 т. Это ограничение простое и записывается как

≤

Ежедневный объем производства краски для внутренних работ не должен

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

чем на одну тонну. Это ограничение можно сформулировать так: разность между

ежедневными объемами производства красок для внутренних и наружных работ не

должна превышать одной тонны, то есть

– x

≤

В-третьих

, еще одно неявное ограничение состоит в том, что переменные x

и x

должны быть неотрицательными. Таким образом, к сформулированным выше

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

≥

0 и x

≥

Математическая модель

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

Максимизировать z = 5x

+ 4x

при выполнении ограничений

+ 4x

≤

24,

+ 2x

≤

Ст

. 15 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

– x

+ x

≤

≥

0, x

≥

Допустимое решение

Любое решение, удовлетворяющее ограничениям модели, является допустимым.

Например, решение x

= 3 и x

= 1 будет допустимым, так как не нарушает ни одного

ограничения, включая условие неотрицательности.

Действительно, подставьте значения x

= 3 и x

= 1 в левые части неравенств

системы ограничений и вы убедитесь, что ни одно неравенство не нарушается.

Значение целевой функции при этом решении будет равно z = 5

3 + 4

1 = 19 (тысяч

долларов).

Оптимальное допустимое решение

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

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

Не так сложно увидеть, что наша задача имеет много (фактически, бесконечно много)

допустимых решений. По этой причине невозможна подстановка значений

переменных для поиска оптимального решения, то есть нельзя применить простой

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

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

В разделе 2.2 показан графический метод нахождения оптимального допустимого

решения для простых задач линейного программирования. Там же объясняются

основные идеи симплекс-метода, используемого в общем случае.

В заключение отметим, что в нашем примере целевая функция и все ограничения

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

предполагает следующее:

Значения левых частей неравенств ограничений и значение целевой функции

прямо пропорциональны значениям переменных.

Аддитивность переменных означает, что общий вклад всех переменных в

значения целевой функции и левых частей неравенств ограничений является

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

Самостоятельная работа

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

Постройте новые ограничения, исходя из следующих условий:

Ежедневный объем производства краски для внутренних работ должен не менее

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

наружных работ.

Ежедневное потребление сырья М2 должно быть не менее 3 т и не более 6 т.

Ежедневный объем производства краски для внутренних работ не может быть

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

Минимальный ежедневный общий объем производства краски обоих типов

составляет 3 т.

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

Ст

. 16 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

общему объему производства краски обоих типов не должно превышать 1/2.

Найдите оптимальное допустимое решение модели среди следующих решений:

= 1, x

= 4.

= 2, x

= 2.

= 3, x

= 1.5.

= 2, x

= 1.

= 2, x

= –1.

3. Для допустимого решения x

= 2, x

= 2 определите:

объем используемого сырья M1;

объем используемого сырья М2.

2.2. Графическое решение задачи линейного

программирования

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

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

последовательность вычислений по некоторым правилам, являются основой

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

отличие от графических методов, они совершенно не наглядны. Графические же

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

которых число переменных равно 2, что дает возможность представить задачу на

плоскости.

Конечно, задача, в которой число переменных равно 2, крайне редко встречается на

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

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

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

Итак, графический способ решения задачи линейного программирования состоит из

двух этапов:

Построение пространства допустимых решений, удовлетворяющих всем

ограничениям модели.

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

решений.

Теперь рассмотрим графический способ решения задачи линейного

программирования для двух вариантов:

ля максимизации и для минимизации

целевой функции.

2.2.1. Нахождение максимума целевой функции

Давайте вспомним модель, которая была построена нами ранее для компании,

производящей краску (см

. раздел 2.1.1). На этом примере подробно рассмотрим оба

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

Этап 1. Построение области допустимых решений

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

на горизонтальной указываются значения переменной x

;

Ст

. 17 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

на вертикальной — x

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

≥

0 и x

≥

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

первом квадранте (то есть выше оси x

и правее оси x

). На рисунке эти ограничения

обозначены цифрами (5) и (6).

Чтобы учесть оставшиеся ограничения, сначала заменим неравенства на равенства.

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

Строим первую прямую (она обозначена на рисунке как линия (1)). Заменим

неравенство 6x

+ 4x

≤

24 уравнением прямой 6x

+ 4x

= 24. Чтобы провести эту

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

= 0,

тогда x

= 24/4 = 6. Аналогично для x

= 0 находим x

= 24/6 = 4. Итак, мы получаем,

что наша прямая проходит через две точки: (0, 6) и (4, 0).

налогично строятся

прямые, соответствующие другим ограничениям (на рисунке они обозначены

цифрами (2), (3) и (4)).

Рассмотрим теперь, как графически интерпретируются неравенства. Каждое

неравенство определяет полуплоскость, которая располагается по одну из сторон

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

одну сторону прямой, удовлетворяют неравенству (допустимая полуплоскость), а

точки, лежащие по другую сторону, — нет.

«Тестовой» точкой, проверяющей, какая полуплоскость является допустимой, а какая

Ст

. 18 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

— нет, может служить точка (0, 0). Например, эта точка удовлетворяет первому

неравенству 6x

+ 4x

≤

24 (здесь 6

0 + 4

≤

24). Это означает, что все точки

полуплоскости, содержащей точку (0, 0), удовлетворяют этому же неравенству. На

нашем рисунке допустимые полуплоскости показаны стрелками.

В том случае, когда точка (0, 0) не удовлетворяет неравенству, допустимой

полуплоскостью будет та, которая не содержит эту точку.

ПРИМЕЧАНИЕ

Ничего «особенного», для наших целей, в точке (0, 0) нет — просто вычисления с ее участием проходят

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

берите, не смущаясь, в качестве «тестовой» любую другую точку.

Этап 2. Нахождение оптимального решения

Точки области допустимых решений, показанной на нашем рисунке (см

. этап 1),

удовлетворяют одновременно всем ограничениям. Эта область ограничена ломаной

линией АВСDЕF. Любая точка, расположенная внутри или на границе области,

ограниченной этой ломаной, является допустимым решением, то есть

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

допустимых решений бесконечно много.

авайте теперь найдем среди них

оптимальное решение, для чего нужно проделать следующее:

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

Найти оптимальное решение.

Итак, сначала попробуем определить направление возрастания целевой функции

z = 5x

+ 4x

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

два разных значения, например 10 и 15. Подставив эти числа вместо z в выражение

целевой функции, получаем уравнения двух параллельных прямых:

+ 4x

= 10 и 5x

+ 4x

= 15.

На рисунке эти прямые показаны штриховыми линиями, а направление возрастания

целевой функции — жирной стрелкой.

Ст

. 19 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

ВНИМАНИЕ

Числа для определения направления возрастания (или убывания) целевой функции нужно подбирать

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

После того, как мы выяснили направление возрастания нашей целевой функции,

начнем мысленно передвигать в этом направлении (в нашем случае «направо—

вверх») одну из полученных прямых параллельно самой себе. Будем проделывать

это до тех пор, пока наша прямая не достигнет «края» области допустимых решений.

Здесь возможны два варианта: «последнее пересечение» нашей прямой с областью

допустимых значений проходит через вершину многоугольника АВСDЕF или по одной

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

из сторон, оптимальное решение существует, но не единственное (их бесконечно

много) — такие случаи на практике встречаются.

В нашем случае пересечением будет точка C, которая

соответствует оптимальному

решению. Эта точка является местом пересечения прямых (1) и (2), поэтому ее

координаты x

и x

находятся как решение системы уравнений, задающих эти

прямые:

+ 4x

= 24,

+ 2x

= 6.

Решением этой системы будет

= 3 и x

= 1,5,

при этом значение целевой функции будет

z = 5

3 + 4

1,5 = 21.

Полученное решение означает, что для нашей компании оптимальным выбором

будет ежедневное производство 3 т краски для наружных работ и 1,5 т —

ля

внутренних работ с ежедневной прибылью в $21 000.

Ст

. 20 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm