Исследование операций (стр. 2 )

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

W= C1x1+C2x2

При увеличении C1 и уменьшении C2 прямая поворачивается по часовой стрелке, при обратных измениениях – против. ( Рисунок ниже ).

 

 

До тех пор, пока прямая не каснется прямых DE или DF , решение Е будет оптимальным, как только наклон выйдет за пределы, оптимальное решение переместится в точки D или F .

Для примера рассмотрим в каких пределах можно изменять C1 при C2 = const,

чтобы решение осталось неизменно.

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

1< C1 < 4

Можно заметить, что как только коэффициент C1 оказвается < 1, то ресурс 2 становится недефицитным, а 4 – дефицитным. Для нашего примера это значит что если доход о одной тонны краски Н станет меньше 1000$ , то наиболее выгодная производственная программа фабрики должна предусматривать выпуск максимального допустимого количества краски В. При этом общее потребление продукта В снизится, что обусловит недефицитность этого ресурса. Соответствующие выводы можно сделать и для случая, если С 1 > 4 .

ЛЕКЦИЯ 3

2.4 Примеры применения методов линейного программирования

Задачи об ассортименте продукции

Пример 1

Фирма выпускает 3 вида продукции. Процесс их производства состоит

из трех операций :

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

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

на каждую операцию – ограниченно :

операция 1 – 430

операция 2 – 460

операция 3 – 420

Прибыль от проданных изделий : 3$, 2$, 5$ ,

Каков наиболее выгодный объем производства каждого из изделий?

Математическая формулировка

а) Управляемые переменные x1, x2, x3 – производство каждого вида продукции за сутки.

б) Целевые функции : W = 3x1 + 2x2 + 5x3

( величина прибыли за сутки )

в) Ограничения : 1x1 + 2x2 + 1x3 < 430 - затраты на1 операцию;

3x1 + 0x2 + 2x3 < 460 - затраты на 2 операцию;

1x1 + 4x2 + 0x3 < 420 - затраты на 3 операцию.

Здесь xj > 0 ( условие неотрицательности переменных ) .

Пример 2 Задача о диете .

20 тысяч цыплят выращиваются до 8 недельного возраста и поступают в

продажу. Средний расход корма, в среднем, 1 фунт(445 г.) в неделю.

Основные компоненты корма показаны в таблице :

Содержание питательных веществ ингридиент фунт/фунт ингридиента Цена $/фунт Кальций Белок Клетчатка Известняк 0,3,04 Зерно 0,001 0,09 0,02 0,15 Соевые бобы 0,002 0,50 0,08 0,40

Смесь должна содержать : кальций [ 0,8 – 1,2 % ]

белка > 22 %

клетчатки < 5 %

Рассчитать наиболее дешевую смесь, удовлетворяющую этим требованиям

Математическая формулировка

а) Управляемые переменные – содержание известняка x1, зерна x2 , бобов x3 (в фунтах).

б) Целевая функция : W = 0.04x1 + 0.15x2 + 0.4x3

в) Ограничения :

x1 + x2 + x3 > 20000 ( объем смеси на 20000 циплят)

 

0.04x1 + 0.15x2 + 0.4x3 > 0.008(x1 + x2 + x3) ( > 0.8 % кальция )

0.04x1 + 0.15x2 + 0.4x3 < 0.012(x1 + x2 + x3) ( < 1.2 % кальция )

0.04x1 + 0.15x2 + 0.4x3 > 0.022(x1 + x2 + x3) ( > 2.2 % белка )

0.04x1 + 0.15x2 + 0.4x3 < 0.05 (x1 + x2 + x3) ( < 5 % клетчатки)

После необходимых преобразований :

x1 + x2 + x3 > 20000

0.372xxx3 > 0

0.368xxx3 < 0

- 0.220xx2 + 0.280x3 > 0

- 0.050x1 + 0.030x2 + 0.030x3 < 0 ; xj > 0, j = 1, 2, 3 .

Пример 3 Задача о расходе и минимизации обрезков .

Крупный ЦБК выпускает бумажную ленту шириной 20 фунтов. По спецзаказам эти рулоны разрезаются по требуемой ширине.

заказ	требуемая ширина	объем заказа
1 2 3	5 7 9	150 200 300

Варианты раскройки рулонов показаны на рисунке :

А

 

3

4

7

9

5

9

7

1

С

5

БРАК

5

5

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

Математическая формулировка .

а) Управляемые переменные : xj , j = 1,…,6 – количество рулонов, разрезаемых по вариантам 1…6 .

Таблица раскроек

требуемая ширина (фут)	вариант раскроя	заказы
5 7 9 потери	1 0 1 1 1	2 1 0 3 3	3 2 0 1 1	4 4 0 0 0	5 1 2 0 1	6 0 0 2 2	150 200 300 --

б) Целевая функция :

W = 4x1 + 3x2 + 1x3 +0x4 + 1x5 + 2x6

в) Ограничения :

 

0x1 + 2x2 + 2x3 +4x4 + 1x5 + 0x6 > 150

1x1 + 1x2 + 0x3 +0x4 + 2x5 + 0x6 > 200

1x1 + 0x2 + 1x3 +0x4 + 0x5 + 2x6 > 360 ; xj > 0, j = 1,…,6

Пример 4 Оптимизации работы сборочного конвейера .

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

цех	фонд раб. времени, ч / неделю	производительность узел / ч
1	100	1 8	2 5	3 10
2	80	6	12	4

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

Управляемые переменные :

Xij - время за неделю (час.), выделяемое в i - м цехе на выпуск j – го узла.

Целевая функция :

(*) min[8x11 + 6x21, 5x12 +12x22, 10x13 + 4x23] max

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

Ограничения :

 

x11 + x12 + x13 < 100 ( ограничения 1-го цеха )

x11 + x12 + x13 < 100 ( ограничения 2-го цеха )

xij > 0, i = 1, 2 j = 1, 2, 3 .

Полученная задача не явлыется задачей линейного программирования, так как (*) нелинейно, однако его можно свести к линейному, введя новую переменную y :

y max

y < 8x11 + 6x21

y < 5x1 + 12x22

y < 10x13 + 4x23

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

Пример 5 Целевое программирование.

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

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

Конкретные пример :

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

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

	производство изделия (час)
станок	1	2
1 2 удельная прибыль	5 4 6 $	6 8 4 $

Математическая формулировка

а) Управляемые переменные

Xj , j = 1, 2, 3 – количество изделий .

б) Ограничения :

Если не учитывать возможность сверхурочных :

 

(x1/5) + (x2/6) < 8 ( станок 1 )

(x1/4) + (x2/8) < 8 ( станок 2 )

Для учета сверхурочных введем переменные y1 и y2 :

ЛЕКЦИЯ 4

Продолжение предыдущей лекции …

 

(x1/5) + (x2/6) - y1 = 8

(x1/4) + (x2/8) – y2 = 8

Если yi < 0, то имеющий фонд времени не израсходован, если yi > 0, то используются сверхурочные в объеме yi часов.

Отметим, что в любом случае yi < 4 – ограничение времени сверхурочных.

Целевая функция :

W = 6 x1 + 4x1 – 5(max ( 0, y1 ) + max ( 0, y2 )) ,

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

w i = max{0, yi}, которые эквивалентны введению условий :

w i > 0, w i > yi

Полная запись модели :

W= 6x1 + 4x2 - 5(w 1 + w 2 ) max

(x1/5) + (x2/6) - y1 = 8

(x1/4) + (x2/8) - y2 = 8

y1 - w 1 < 0

y2 - w 2 < 0

y1 < 4

y2 < 4

x1, x2, w1, w 2 > 0

y1 y2 - не ограничены

2.5 Задача ЛП-как задача распределения ресурсов .

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

W=C1x1+…+Cnxn max ( 1 )

a11x1 + … + a1nxn < b1

… … … … … ( 2 )

am1x1 + … + amnxn < bm1

x1 … xn > 0

Здесь x1 … xn рассматриваются как n видов деятельности, для проведения которых используется m ресурсов, запасы которых b1, … , bm .

aij – расход i – го ресурса на j – производства.

Cj – прибыль от единицы продукции j – го производства.

2.6 Симплекс – метод решения задачи ЛП .

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

допустимых решений (ОДР).

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

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

Процедура СМ может быть сформулирована следующим образом:

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

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

В задаче о краске целевая функция выглядит : Z = 3xH+2xB max .

Коэффициент через xH больше, значит нужно увеличивать эту переменную, следовательно новым опорным пленом будет точка В .

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

2.6.1 Стандартная ( каноническая ) форма записи задачи Л. П.

В стандартной форме записи задачи Л. П. :

1)  Все ограничения записываются в виде равенств с неотрицательной правой частью.

2)  Все переменные неотрицательные.

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

а) Ограничения неравенства вида <, например,

x1+2x2 < 6

преобразовывают, прибавляя остаточную переменную например S1 > 0 :

x1+2x2 + S1 =6, S1 > 0

б) Ограничения неравенства вида >, например,

3x1+2x2 - 3x3 >5,

преобразовывают, вычитаем избыточную переменную например S2 > 0

3x1+2x2 - 3x3 – S2 = 5, S2 > 0

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

в) Если правая часть получившихся уравнений – отрицательна, наприме:

2x1+3x2 - 3x3 – S2 = -5, то обе части уравнения на -1

-2x1 - 3x2 + 3x3 + S2 = 5 .

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

(*) yi=yi' – yi'', yi', yi'' > 0

После решения задачи, переменную yi ( а она имеет вполне определенный смысл ) , рассчитывают по формуле (*) . Отметим что при любом допустимом решении только одна из переменных может быть положительной. То есть если yi' > 0, то yi'' = 0 , и наоборот. Поэтому yi' называют остаточной, yi'' избыточной.

2.6.1 Опорные планы симплекса.

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

 

Z= 3xH + 2xB + 0*S1 + 0*S2 + 0*S3 + 0*S4

xH + 2xB + S1 = 6

2xH + xB + S2 = 8

- xH + xB + S3 = 1

xB + S4 = 2

xH, xB, S1, S2, S3, S4 > 0

При Si = 0 ограничения модели описывают ребра симплекса – область допустимых решений :

XB

S4=0

E

D

2