Шелобаев С.И. Математические методы и модели

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

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

чений

Х]

и Xj (оптимальным решением задачи без учета требований це-

лочисленности являются координаты точки А (2,8; 4,3), приведенные в

табл. 3.1. Однако эти значения Х| и xj в точке А требованиям целочис-

ленности не удовлетворяют, поэтому получить целочисленное решение

можно путем округления полученных непрерывных значений Округ-

ленные координаты, принадлежащие точке В (3;4), оказываются за пре-

делами области допустимых решений. В точке С (3;3) мы получим до-

пустимое решение. Поэтому остается еще одна точка i)(2;4), являю-

щаяся оптимальным решением задачи

= 6), но не являющаяся бли-

жайшей к непрерывному оптимальному решению.

На основании решения рассмотренного примера можно сде-

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

переменных в непрерывном решении даже в меньшую сторону

может привести к недопустимому решению; б) оптимальным

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

ром значения переменных не являются ближайшими к опти-

мальному решению непрерывной задачи.

Таблица

3.1.

Результаты решения примера

3.1

Точка оптимального

решения задачи

Х| Х2 F

Решение

2,8

4,3

5,14

—

3,9

4,6

Непрерывное

Недопустимое

Допустимое

Оптимальное

Таким образом, оказывается, что решение целочисленных

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

ния оптимального решения подобных целочисленных задач ис-

пользуются специальные методы с учетом конечности числа

возможных решений любой целочисленной задачи.

Так, например, в задаче с переменными х\ и х^, удовлетво-

ряющими граничным условиям О < Х] < 4; О < хг <5, число

возможных решений Л'^ может составить: N = 4*5= 20. При

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

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

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

(являются ли допустимыми решениями) и выбрать затем из них

наилучшее в смысле принятой целевой функции. __

Подобный метод характеризуется высокой трудоемкостью

операций перебора при росте числа переменных и расширении

(3.3)

области фаничных условий. Поэтому для решения реальных за-

дач прибегают к эвристическим методам, в которых все множест-

во альтернатив не рассматривается. Наиболее распространен ме-

тод ветвей и границ, применение которого рассмотрим на сле-

дующем примере.

Пример

3.2. Пусть целочисленная задача имеет математическую мо-

дель вида (3.3). Необходимо найти ее оптимальное решение.

/^ = 7x1+ 3x2-* max;

5x1 +

2x2

20;

8x1 +

4x2^38;

xi,X2^0 - целые.

Решение. Решение задачи разобьем на ряд подзадач. Эту за-

дачу без наложения требований целочисленности назовем

задачей

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

найдем оптимальное решение: это —точка А с координатами

х {

= 1,

Х2 = 7,5 и fi

29,5 (верхний индекс у переменных и нижний у целе-

вой функции соответствуют номеру задачи). Однако из полученного

решения видно, что

Х2

= 7,5 не удовлетворяет требованию целочислен-

ности, поэтому для дальнейшего решения составим следующие две за-

дачи

{задачи

2 и 3) с граничными условиями, исключающими возмож-

ность получения

Х2

= 7,5:

Задача

= 7x1 + 2x2

5x1 + 2x2 S

20;

8x1 +

4x2^38;

XI SO; 0^X2^7

max;

7x1+ 3x2-

5x1 + 2x2

^ 20;

8x1 +

4x2^38;

xi^O;

Х2^8.

Решение непрерывных задач 2 и 5 позволяет получить следующие

значения: х? = 1,2; х^ = 7; /^ = 29,4; xj = 0,75; х^ = 8; /"з = 29,25. Од-

нако из полученных результатов видно, что в обеих задачах вновь на-

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

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

(задачи

4н 5

—для задачи

2и

задачи

6и

7-для

задачи

3), но с ограничениями на граничные условия

переменной

(рис. 3.1, табл. 3.2).

В табл. 3.2 приведены результаты решения непрерывной за-

дачи 1 и задач 4—6, удовлетворяющих требованиям целочислен-

ности, из анализа которых следует:

а) решение задачи 4 наиболее близко к непрерывному по

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

б) оптимальным является решение задачи 5, в котором зна-

чения переменных существенно отличны от значений непре-

рывного решения;

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

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

задачи.

Х2

й7

Задача

Г.

Xi°l; х^=7,5; F=29,5

Х2^8

Х,^1

Задач!

=1,2;

xj=/

22:

'; /-=29,4

Задача 4:

х,=1,

х^-Т;

/•=28

;с,>2

Задача 5:

x^—2•,

Xj=5;

/•=29

Задача 3:

х,°0,75;

л^=8; /^29,25

х,=0

Задача

Х|=0;

Xj=9;

F=n

Xl^l

Задача

Т.

несов-

местна

Рис. 3.1.

Алгоритм решения

гримера 3.2

по

методу

ветвей

границ

Таблица

3.2.

Результаты решения задачи

Задача

Х2

7,5

29,5

Метод ветвей и фаниц позволяет накладывать требования

целочисленности на любое число переменных: а) при наложе-

нии его на все переменные, входящие в модель, получают полно-

стью целочисленное решение; б) при наложении его на часть

переменных

—

частично целочисленную задачу, которую следует

также решать с помощью метода ветвей и границ (при этом до-

полнительные требования на фаничные значения непрерывных

переменных накладывать не следует).Схему расчета задач на ос-

нове метода ветвей и фаниц часто называют принятием решения

на дереве возможных вариантов.

Заметим, что к многочисленным процессам, описываемым

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

процессы разнообразного (линейного, объемного, комплектного,

позаказного и т.п.) раскроя различных материалов — изготовле-

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

дов,

самолетов и др. Раскрой может осуществляться как самой

ЭВМ, так и человеком, принимающим ряд вариантов раскроя с

последующим отбором ЭВМ наилучшего из них. Считается, что

в любой ситуации ЭВМ должна выбирать аналогичные варианты

раскроя. Более подробно анализ этих ситуаций, составление ма-

тематических моделей задач данного класса и их решение рас-

смотрены в [78,82 и др.].

В целом целочисленные задачи имеют достаточно широкую

сферу применения, включая раскрой материалов, планирование

и производство крупных изделий и др.

Задачи целочисленного программирования с булевыми перемен-

ными. Во многих практических случаях искомые переменные Xj

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

О, либо 1. Такие переменные называют

булевыми

(чтобы отличать

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

раз

Ху[0;1]

при их упоминании, будем обозначать их 5,)- С помо-

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

нию задачи, связанные с процессами выбора различных вариан-

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

класс задач более подробно.

Задачи выбора вариантов. Особенности решения данной зада-

чи проиллюстрируем на решении следуюш1его примера.

Пример

3.3. Чтобы получить прибыль, нам необходимы материаль-

ные и трудовые ресурсы, при этом возможны четыре варианта расхода

ресурсов и получения прибыли (табл. 3.3). Требуется определить, какие

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

принятых вариантов к не превышало трех {к < 3).

Таблица 3.3.

Исходные данные примера

3.3

Показатели Варианты

Наличие ресурса

1 2 3 4~

Прибыль 65 80 90 210 —

Pecypcbj:

материалы 200 180 240 250 800

трудовые 10 15 22 28 50

Таблица 3.4. Ряд условий

решения примера

Вариант

решения Логические условия

Прибыль

5з

Нет

300

52 = б4

290

8з

+ 54=1

235

(3.4)

Решение. Для составления математической модели задачи

принимаем, чтоу-му варианту соответствует переменная 5у (/ = 1,4 ).

При этом bj= 1, еслиу-й вариант принимается, и бу = О, еслиу'-й ва-

риант не принимается. Тогда имеем математическую модель вида:

655,

80б2

908з

21084 ^ шах;

2005,

18052

2405з

25054 ^ 800;

105,+ 1552+ 2253 + 2854 ^50;

5i + 52 + 5з + 54

Последняя строка системы (3.4) отражает дополнительное

требование, что общее число принятых вариантов не превышает

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

табл. 3.4, откуда видно, что наибольшая прибыль F = 300 полу-

чается, если принимаются варианты 3, 4. С помощью булевых

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

условия связи-между вариантами (например, если потребовать,

чтобы варианты 2

4 принимались только вместе, то данное

условие можно записать как бг = 64 или в форме записи ограни-

чений, как

52 — 54

= 0; если потребовать выбора только одного из

вариантов 3 или

то это условие можно записать так: 5з +

= 1).

Результаты решения задачи с учетом этих условий сведены так-

же в колонки 2 и 3 табл. 3.4, откуда видно, что введение этих

логических условий снижает уровень прибыли.

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

F =

Y,cjbj

-> max(min);

/=1

(а)

(3.5)

XSy

^ к.

>='

данной системе ограничение (а) может учитывать самые

разнообразные условия и требования, например:

а) «должен», при этом в офаничениях ставится знак равен-

ства; «может»—знак неравенства;

б) логической функции «И»(«ИЛИ») —делается запись вида:

У=1

I5>=1

7=1

в)

выбор

вариантов 1 и 3 —запись вида 5i + 5з ^ 1;

г)

выбор

варианта 1 или 3 («ИЛИ искл.»), т.е. из двух вариан-

тов надо принять любой один —запись вида 5i + 5з = 1;

д) обозначив 5б —«быть», 5„

—««е быть», альтернативу

«быть или не быть» можно записать как 5б + 8„.б = 1 (в этом

случае есть два допустимых решения: 1) 5б = 1; бн.б = О» что оз-

начает

«быть»;

2) бб = 0; 8„.б = 1 — «ие

быть»).

Так как целевая

функция еще не сформулирована, то принять верное решение

пока невозможно.

Задачи дискретного программирования. В данной ситуации ре-

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

ступают только целые, но лишь определенные числа. Поясним

это на примере.

Пример

3.4. Допустим, что субъект хозяйствования выпускает ме-

бельные наборы — диваны, кресла и стулья. Требуется определить,

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

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

и трудовых ресурсов (табл. 3.5) по критерию максимума общего дохода.

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

мать любое целое значение, подлокотники кресел изготавливают пара-

ми

—

они должны быть кратными 2, а ножки стульев

—

Решение. С учетом сформулированных требований матема-

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

Таблица

3.5.

Исходные данные для решения примера

3.4

Требуемые

ресурсы

Цена

Древесина

Трудовые ресурсы

Спинка

дивана

Комплектующие

изделия

Обозначение

Подлокотник

кресла

комплектующих

Х2

Ножка

стула

хг

Количест-

во наличных

ресурсов

100

f = 20x1+ 6>2 +8x3-»

10x1 + 5x2 +

3x3^100;

2x1

+ 7x2

4x3^50;

О < XI

^10; 0^X2^8;

0^хз<12.

max;

(3.6)

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

Х2

2521

+ 4522

••"

6523 "^ 8524;

хз = 45з, + 85з2 + 125зз,

где

521

522 ••" 523

524

= 1;

5з1

+ 5з2 + 5зз = 1.

Эти булевые переменные реализуют условия выпуска ком-

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

(применительно к подлокотникам кресел переменная Х2 может

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

521 = 1, а остальные 621 = бгз = 524 = О, то

Х2

= 2; если 522 = 1> з

остальные 52i = 52з = 524 = О, то хг = 4 и т.п.). Для учета допол-

нительных условий введены еще семь переменных и четыре ог-

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

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

подлокотников и ножек) только для одного изделия, то можно

было бы записать: хг = 2xi; хз = 4х| и не вводить дополнитель-

ных ограничений и булевых переменных, а это —другая задача).

В результате решения задачи (3.6) на ЭВМ получены сле-

дующие значения: F= 320; Х] = 10;

Х2

= 4; хэ = 12; 522 ~ 5зз = 1;

521 ~ 823 = 524 = 5з] = 5з2 = 0. При этом оказалось, что ресурсы

избыточны: резерв древесины составил 44, а трудовых ресур-

сов

—

4 ед. (такая ситуация характерна для целочисленных за-

дач:

ресурс избыточен, но его недостаточно для увеличения вы-

пуска продукции).

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

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

запись:

EQ5

OiJ

•

Xj 2

k=\

bik S Л

/•-*

*/,

5л-

max(min);

/ = l,m;

j = Un;

(3.7)

где dij, djj,...,

d;i^

—дискретные значения, которые может принимать пе-

ременная Xj.

Система (3.7) отличается от обычной задачи распределения

ресурсов, имеющей вид (3.8), тем, что в ней добавлены булевые

переменные и увеличено число ограничений (при этом под-

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

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

оказывается увеличение размерности задачи и ее целочислен-

ность):

F =

Y^CjXj

-^ max(miii);

dj^Xj i Dj.

(3.8)

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

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

блема выбора наилучшего из набора вариантов.

В целом задачи с булевыми переменными можно решать: а)

как обычные задачи целочисленного программирования с при-

менением метода ветвей и границ (при этом на каждую пере-

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

пределах

5у

[0;1] и иметь целые значения

— О

или 1); б) методом

полного, или сплошного, перебора. Рассмотрим применение

метода полного перебора

на примере.

Пример

3.5. Необходимо решить задачу с булевыми переменными,

описываемую следующей системой:

/" = 351-252+ 5бз-

5i+ 252-53 ^2; (а)

+452+ 53^4; (б)

+ 52

(в)

+ 5з

(г)

max;

(3.9)

Так как переменные 5], bj,

могут принимать значения

или

в лю-

бом сочетании, то рассмотрим их всевозможные комбинации (табл. 3.6).

Алгоритм при полном переборе имеет следующий вид [78,82]:

Таблица

3.6.

Исходные данные

дополнительные условия

для решения гримера

3.5

BapuoHi

Число

т Пере

Требования

менные

5, 8з

0 0

1 0

0 1

-1

£ 2

Условия

(2)

£4

Таблица 3.7. Рост

операций при росте

переменных

ело

160

5120

(3)

пит

(4) F

0 0

4 3

0 -2

1 5

5 8

< 6 max

ограничений т

352

11264

120

512

16384

Заполняются в таблице все возможные варианты сочетаний до-

пустимых значений 5i, 62, 63.

Определяются значения левых частей ограничений (а)—(г) сис-

темы (3.9) и целевой функции.

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

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

в вариантах 4, 7 и 8, которые исключаем из дальнейшего рассмотрения

как приводящие к недопустимым решениям).

Из оставшихся вариантов принимается тот, в котором целевая

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

рианте 6 F = 8, при этом он является оптимальным вариантом, имею-

щим характеристики: 5i = 1; бг = 0; 5з = 0; /"= 8).

В общем случае число вычислительных процедур при полном пе-

реборе быстро возрастает (табл. 3.7) и составляет число N =

2''(/я

+ 1),

где я —число переменных, т —число ограничений.

Так, например, анализ примера (3,5) показывает, что из воз-

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

числить четыре ограничения и целевую функцию и в целом вы-

полнить 40 вычислительных операций: 8(4 + 1) = 40.

Сокращения трудоемкости процедурьу полного перебора

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

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

тивного фильтра, метод Балаша с фильтром и др.

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

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

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

решений можно рассматривать как решение задач оптимизации,

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

моделью которых выступает задача линейного профаммирова-

ния, в которой переменные величины ау,

Ь/,

cj являются строго

детерминированными при их точных и известных значениях.

Однако на практике такая определенность существует редко:

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

сов и реализации товаров (данные параметры, в свою очередь,

зависят еще от множества случайных внешних и внутренних

факторов —вьщеленных фондов, соответствия качества ресурса

предъявляемым требованиям, своевременности и полноты по-

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

др.),

которые физически заранее определить просто невозмож-

но;

причем чем больше период планирования или прогнозиро-

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

оценке возможных значений ресурсов

Ь(,

норм расхода ау, ко-

эффициентов целевой функции с,. Однако и в этих ситуациях

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

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

(благоприятные и не совсем) ситуации с помощью методов тео-

рии вероятностей.

Так как случайные величины или процессы описываются ко-

личественными характеристиками (математическим ожиданием,

дисперсией, средним квадратическим отклонением, коэффици-

ентом вариабельности и др.) или законами распределения, то

рассмотрим особенности составления математических моделей и

решения задач оптимизации и распределения ресурсов в услови-

ях неопределенности.

Задачи оптимизации распределения ресурсов с учетом неопре-

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

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

держанию

—

к задачам распределения ресурсов и в условиях ре-

альной жизни величины а,у, А,, с, математической модели задачи

распределения ресурсов оказываются случайными, то ЛПР вы-

нуждено решать задачи не линейного, а

стохастического

про-

граммирования (СТП).