ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
создание документов онлайн
Документы и бланки онлайн

Обследовать

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





















































ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

математике



Отправить его в другом документе Tab для Yahoo книги - конечно, эссе, очерк Hits: 765



дтхзйе дплхнеофщ

Условный экстремум ф-ции нескольких переменных
Указать grad U в точке M0
ВОЛHОВАЯ ТЕОРИЯ ЭЛЛИОТТА В КРАТКОМ ИЗЛОЖЕHИИ
Зонная теория твердого тела.
Решение транспортной задачи. Матричные игры
Введение в диалектику математических понятий
Поэлементное деление отрезка в крайнем и среднем отношении
Исторические справки. Матрицы.
Численные методы решения дифференциальных уравнений
ПРИБЛИЖЕННЫЕ РЕШЕНИЯ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ
 

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

 

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

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

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

Либо:

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

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



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

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

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

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

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

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

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

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

 

 

 

 1.  Задача о распределении ресурсов.  Максимизация дохода.

 

Рассмотрим построение модели на следующем простом примере. Пусть некоторая компания выпускает продукцию двух видов: продукт №1 и продукт № Известен удельный расход ресурсов на единицу каждого продукта и доход, получаемый в результате ее реализации. Имеются два вида ресурсов: материалы в количестве 10 единиц, и труд в количестве 36 часов. Данные представлены в следующей таблице:

Виды ресурсов

Затраты на 1 ед. продукции

Имеющиеся ресурсы

Продукт №1

Продукт №2

Материалы

1

2

10 ед.

Труд

6

6

36 ч.

Доход

4

5

 

 

Согласно таблице, изготовление единицы продукта №2 требует 2-х единиц материалов и 6 часов рабочего времени. При этом реализация единицы данного продукта обеспечивает 5 единиц дохода. Соответствующие данные приведены и по 919i88bj продукту №1.

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

В рассматриваемом примере компания имеет дело с ограничениями двоякого рода: ограничениями по ресурсам и ограничением по спросу. Если бы их не было, разумной стратегией компании было бы неограниченное увеличение выпуска продукции, поскольку каждая дополнительная единица продукции приносила бы дополнительный доход. Именно ограничения заставляют компанию искать оптимальную комбинацию объемов выпусков продукции №1 и №

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

Управляемыми переменными в этой задаче являются объемы выпуска продукции каждого типа. Обозначим через Х1 и Х2 объемы выпуска продукта №1 и продукта №2 соответственно.

Выразим цель компании через управляемые переменные. Поскольку, в соответствии с таблицей, единица продукта №1 приносит  4 единицы дохода, то Х1 единиц продукта №1 приносят 4Х1 единиц дохода, и соответственно Х2 единиц продукта №2 приносят 5Х2 единиц дохода. Следовательно, в сумме оба вида продукции дадут доход, равный 4Х1+5Х Этот доход компания стремится максимизировать, что можно записать так:

 4Х1 + 5Х2   Þ  max

Выпишем ограничения задачи. Так как каждая единица продукта №1 требует одной единицы материалов, то Х1 единиц продукта потребует 1Х1 единиц материалов. Соответственно, Х2 единиц продукта №2 потребуют 2Х2 единиц материалов. Общее количество материалов, которыми располагает компания - 10 единиц. Следовательно, суммарный их расход, 1Х1+2Х2, не должен превышать указанного количества:

1 + 2Х2   £  10

Аналогично по второму ограниченному ресурсу - труду. Суммарное его потребление 6Х1+6Х2, при изготовлении продукции в количествах Х1 и Х2, не должно превышать имеющихся возможностей в 36 часов:

1 + 6Х2   £  36

Рыночное ограничение по спросу на величину производства Х1   продукта №1 в количестве не более 4-х единиц записывается очевидным образом:

Х1  £  4

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

Х1  ³  0,   Х2  ³  0.

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

Найти объемы производства Х1 и Х2, обеспечивающие компании максимальный доход

  

Z = 4Х1+5Х2 Þ max

  

при условиях:

1 + 2Х2  £  10       (расход материалов)

1 + 6Х2  £  36       (затраты труда)

Х1  £  4                     (спрос)

Х1  ³  0,  Х2  ³  0.    (неотрицательность)

Задача может быть решена графическим методом.

 

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

1 + 2Х2  =  10

1 + 6Х2  =  36

Х1  =  4

Х1  =  0,  Х2  =  0.

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

Чтобы определить, в какой точке прямая  1Х1+2Х2=10  пересекает ось Х1, нужно принять  Х2=0,  и в результате получим  Х1=10.  Затем примем Х1=0, чтобы определить точку пересечения с осью Х2, и получим Х2=5. 

Действуя таким же образом, найдем, что прямая 6Х1+6Х2=36 пересекает оси координат в точках  (Х1=6, Х2=0)  и (Х1=0, Х2=6).

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


                                                              

8

6

4

2

Х1

0

2

4

6

8

Х1 + 2Х2 = 10

 
                                                                   

Согласно условиям задачи, область допустимых решений располагается правее оси Х2 (поскольку Х1³ 0), выше оси Х1 (т.к. Х2³ 0), левее вертикальной прямой Х1=4 (Х1£ 4), и ниже двух прямых  1Х1+2Х2=10  и  6Х1+6Х2=36  (поскольку 1Х1+2Х2£ 10 и 6Х1+6Х2£ 36). Таким образом, областью допустимых решений является многоугольник ЕАВСD.

В качестве примеров рассмотрим несколько точек, помещенных в систему координат. Точка Q (Х1=8, Х2=8) удовлетворяет лишь ограничениям Х1³ 0 и Х2³ 0, и поэтому не попадает в область допустимых решений. Точка Р (Х1=5, Х2=1) удовлетворяет всем ограничениям, кроме Х1£ 4, и она также не попадает в область допустимых решений. Точка R (Х1=2, Х2=2) удовлетворяет всем ограничениям и, следовательно, располагается в области допустимых решений. Точки, расположенные в многоугольнике (Е А В С D), в его вершинах и на его гранях, также находятся в области допустимых решений.

Необходимо определить: какая точка из множества точек, расположенных в области ЕАВСD, является оптимальной с позиций дохода Z?  Т.е. в какой допустимой точке (Х1, Х2) величина дохода, определяемая выражением  Z=4Х1+5Х2,  является максимальной?

Построим в той же системе координат линии целевой функции  Z=4Х1+5Х2, соответствующие различным значениям дохода Z. Какие бы значения Z мы ни взяли, линии будут проходить параллельно. Чем больше значение Z, тем выше проходит линия целевой функции.

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


                                       

8

6



4

2

Х1

0

2

4

6

8

        

Линия, соответствующая значению дохода Z=40, и пересекающая оси координат в точках  (Х1=10, Х2=0)  и     (Х1=0, Х2=8)  проходит выше области допустимых решений. Следовательно, эта величина дохода является недостижимой при заданных условиях.

Теперь проведем линии Z, параллельные первой, и проходящие через вершины В и С. 

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

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

Точка В образуется пересечением прямых  1Х1+2Х2=10  и  6Х1+6Х2=36. Поэтому, чтобы найти значение Х1 и Х2 в точке В, необходимо решить систему двух уравнений:

1 + 2Х2 = 10

1 + 6Х2 = 36

Преобразуем первое уравнение:

Х1 = 10 - 2Х2

Подставив Х1 во второе уравнение, получим:

6 ´ (10 - 2Х2) + 6Х=  36,

60 - 12Х2 + 6Х=  36,

-6Х2  = -24,

Х2 = 4.

Подставляя найденное значение Х2 в уравнение Х1=10 - 2Х2, получим:

Х1 = 10 - 2 ´ 4  =  2

Таким образом, точка В имеет координаты  (Х1=2, Х2=4),  или, более кратко, В=(2, 4).

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

Z  =  4Х1 + 5Х2  =  4 ´ 2  +  5 ´ 4 = 28 ед.

Таким образом, задача решена. Найдены и точка оптимального решения - объемы выпуска продукции Х1 и Х2, и величина максимального дохода Z.

 

 

 

  Минимизация затрат

 

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

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

Содержание обоих витаминов в продуктах различно, различна и цена:

 

 

Витамины

Яйца

Морковь

Суточная

потребность

А

2

4

16 мг.

В

3

2

12 мг.

Стоимость

4

3

 

Каждое яйцо обеспечивает 2 мг. витамина А и  3 мг. витамина В. Стоимость яйца - 4 ед. (Аналогичные данные по моркови приведены в 3-й колонке). Все данные условны.

Примем за Х1 количество яиц, которое придется съесть, и за Х2 - количество морковок. Тогда 2Х1 - это количество витамина А, доставляемого съеденными яйцами, а 4Х2 - количество того же витамина, доставляемое морковками. Общее количество витамина А, доставляемое обоими продуктами, не должно быть меньше минимальной суточной потребности в 16 мг. Однако превышение этой потребности допускается:

1 + 4Х2   ³  16

Такое же условие записывается и для витамина В:

1 + 2Х2   ³  12

Условие неотрицательности:

Х1  ³  0,   X2  ³  0.

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

 

Z = 4X1 + 3X2   Þ  min

 

Задача формулируется следующим образом:

Определить объемы суточного потребления Х1 и Х2 обоих продуктов, при которых достигаются минимальные затраты                  Z = min  с соблюдением условий (ограничений) по обязательным нормам суточного потребления:

1 + 4Х2   ³  16

1 + 2Х2   ³  12

Х1  ³  0,   X2  ³  0.

Эту задачу можно решить графическим методом, так же как и предыдущую.

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

1 + 4Х2   =  16

1 + 2Х2   =  12

Х1 = 0,  X2  =  0.

Чтобы определить, в какой точке прямая  2Х1+4Х2=16  пересекает ось Х1, нужно принять  Х2=0,  и в результате получим  Х1=8.  Затем примем Х1=0, чтобы определить точку пересечения с осью Х2, и получим Х2=4. 

Действуя аналогично, найдем, что прямая  3Х1+2Х2=12  пересекает оси координат в точках  (Х1=4, Х2=0)  и (Х1=0, Х2=6).

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


           

8

6

4

2

Х1

0

2

4




6

8

                                                     

                                 

Согласно условиям задачи, область допустимых решений располагается правее оси Х2 (поскольку Х1³ 0), выше оси Х1 (т.к. Х2³ 0), и выше двух прямых  2Х1+4Х2=16  и  3Х1+2Х2=12  (поскольку 2Х1+4Х2³ 16 и 3Х1+2Х2³ 12). Таким образом, областью допустимых решений является область с вершинами C, D и E,  неограниченная сверху.

Необходимо определить: какая точка  (Х1, Х2) из множества точек, расположенных в области CDE, является оптимальной, т.е. в какой из них достигается минимум затрат Z?

Построим линии целевой функции  Z=4Х1+3Х2, соответствующие различным значениям дохода Z, в той же системе координат. Какие бы значения Z мы ни взяли, линии будут проходить параллельно. Чем ниже значение Z, тем ниже проходит линия целевой функции.

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


 

8

6

4

2

Х1

0

2

4

6

8

                                                     

                                 

Линия, соответствующая значению затрат Z=12, и пересекающая оси координат в точках  (Х1=3, Х2=0)  и   (Х1=0, Х2=4),  проходит ниже области допустимых решений. Следовательно, такая низкая величина затрат является недостижимой при заданных условиях.

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

Точка D образуется пересечением прямых   2Х1+4Х2=16  и  3Х1+2Х2=1  Поэтому, чтобы найти координаты (Х1, Х2) точки В, необходимо решить систему двух уравнений:

1 + 4Х2 = 16

1 + 2Х2 = 12

Преобразуем первое уравнение:

1 = 16 - 4Х2,

Х1 = 8 - 2Х2

Подставив Х1 во второе уравнение, получим:

3 ´ (8 - 2Х2) + 2Х= 12,

24 - 6Х2 + 2Х=  12,

-4Х2  = -12,

Х2 = 3.

Подставляя найденное значение Х2 в уравнение Х1=8 - 2Х2, получим:

Х1 = 8 - 2 ´ 3  = 

Таким образом, точка D имеет координаты  (2, 3).

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

Z  =  4Х1 + 3Х2  =  4 ´ 2   +  3 ´ 3 = 17 ед.

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

 

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

 

 

 

 

 

 

 

3.  Планирование работы цеха

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

                                                                                                                                                  

Станок 1

Станок 2

Станок 3

Станок 4

Изделие 1

10 мин.

®

12 мин.

®

14 мин.

®

10 мин.

® 16 руб

Изделие 2

7 мин.

®

16 мин.

    12 руб

Изделие 3

11 мин.

13 мин.

®

21 мин.

® 14 руб

400 мин.

380 мин.

420 мин.

450 мин.

Так, например, изделие №3 обрабатывается на первом станке 11 мин., не требует обработки на втором станке, обрабатывается в течение 13 мин. на третьем станке и 21 мин. - на четвертом. Полезное нормативное время работы станков за смену (полученное путем исключения времени на их технологическое обслуживание) составляет 400, 380, 420 и 450 мин. - для  1-го, 2-го, 3-го и 4-го станков соответственно.

Каждое изготовленное изделие №1 приносит прибыль в размере 16 руб., изделие №2 - 12 руб., изделие №3 - 14 руб.

Имеется постоянный заказчик изделия №3, которое, в соответствии с контрактом, необходимо производить в объеме не менее чем 12 шт. за смену. Кроме того, изучение спроса показало, что более чем 6 шт. изделия №2 производить нецелесообразно.

Теперь запишем все эти условия в математическом виде.

Если Х1, Х2 и Х3 - производимые объемы изделий №1, №2 и №3, то для первого станка:

10Х1 + 11Х3   £  400 мин,

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

Для второго станка:

12Х1 + 7Х2   £  380 мин.

Для третьего станка:

14Х1 + 16Х2 + 13Х3   £  420 мин.

Для четвертого станка:

10Х1 + 21Х3   £  450 мин.

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

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

16Х1 + 12Х2 + 14Х3   Þ  max

Ограничения на объем выпуска Х3, определяемые условиями контракта, и на Х2, обусловленное рыночным спросом:

Х3  ³  12,   Х2  £  6

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

Х1  ³  0,   X2  ³  0,   X3  ³  0.

Дадим формулировку задачи:

Определить суточные объемы производства Х1, Х2 и Х3  продуктов №1, №2 и №3, при которых достигается максимальный доход Z = max - при условиях, что суммарное время работы каждого станка в течение суток не превысит нормативного значения (ограничения), и при этом будут соблюдаться ограничения на объемы  пр-ва Х2 и Х3:

10Х1 + 11Х3   £  400 мин,

12Х1 + 7Х2   £  380 мин.

14Х1 + 16Х2 + 13Х3   £  420 мин.

10Х1 + 21Х3   £  450 мин.

X3  ³ 12,    X2  £ 6

Х1,  Х2,  Х3    ³  0

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

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

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

 

 

 

 



4.  Разработка графиков дежурств

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

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

     

36

36

30

24

21

24   

12

12

12

        t

0:00

4:00

8:00

12:00

16:00

20:00

24:00

 

 

 

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

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

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

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

Если 1-я смена работает в интервале 8-16 ч., то из приведенного графика потребности города в бригадах врачей, следует, что в 1-ю смену должно выйти 30 бригад.

Если 16-24 ч.  -  2-я смена, то требуется 36 бригад.

Если  0-8 ч.   -  3-я смена, то необходимо 24 бригады.

Всего, таким образом, в течение суток должно выйти:

30 + 36 + 24 = 90 бригад.

 

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

Предположим, допустимо начинать смены в 4, 8, 12, 16, 20, 24 часа. Чтобы сделать более наглядным процесс построения математической модели, нарисуем круг, соответствующий cуткам, а на нем - все возможные варианты начал 8-часовых смен. Всего получается 6 вариантов:


         

                      

На этой диаграмме:

Х1 - количество бригад, заступающих на дежурство в 0 часов,

Х2 -   -/- в 4 часа,

Х3 -   -/- в 8 часов,

Х4 -   -/- в 12 часов,

Х5 -   -/- в 16 часов,

Х6 -   -/- в 20 часов.

Из этой диаграммы видно, что, например, в интервале от 4-х до 8 часов работают бригады, вышедшие в в 0 часов и в 4 часа.

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

в интервале 0-4 ч.            Х1 + Х6   ³  12

в интервале 4-8 ч.            Х1 + Х2   ³  24

в интервале 8-12 ч.           X2 + X3   ³  30

в интервале 12-16 ч.         X3 + X4   ³  21

в интервале 16-20 ч.         X4 + X5   ³  36

в интервале 20-24 ч.         X5 + X6   ³  12

Разумеется,  Х1, Х2, Х3, Х4, Х5, Х6  ³  0

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

Х1 + Х2 + Х3 + Х4 + Х5 + Х6  Þ  min

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

Решение, полученное с помощью компьютерной программы, выглядит следующим образом:  Х1=0, Х2=30, Х3=0, Х4=36,  Х5=0, Х6=1 Это значит, что 8-часовые смены дожны начинаться в 4, 12 и 20 часов, и это потребует  30+36+12=78  бригад «Скорой помощи» в течение суток. Это на 12 бригад меньше, чем в первоначальном варианте.

 

 

 

 

 

5.  Задача об инвестициях

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

Перечислим возможные способы:

1. Акции - S (stocks)

 Облигации - B (bonds)

3. Сберегательные сертификаты - C (certificates of saving)

4. Банковские депозиты - D (deposits)

5. Неинвестированные средства - I (idle)

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

Условия инвестирования по каждому из этих способов следующие:

1. Вложения в акции возможны в начале каждого года. Каждый вложенный рубль возвращается через 2 года с коэффициентом 1,3.

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

3. Вложения в сертификаты возможны всего один раз - в начале 1-го года. Помещенные в них средства возвращаются через 4 года с коэффициентом 1,7.

4. Помещение средств на банковские депозиты возможно лишь в начале 4-го и 5-го года. Средства возвращаются через год с коэффициентом 1,

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

1-й год

2-й год

3-й год

4-й год

5-й год

S1

S2

S3

S4

B1

B2

B3

C1

D4

D5

I1

I2

I3

I4

I5

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

S1,... S4 - вложения в акции в 1-м,... 4-м годах.

B1,... B3 - вложения в облигации в 1-м,... 3-м годах.

C1 - вложения в сертификаты во 1-м году.

D4, D5 - помещение средств на депозиты в 4-м и 5-м годах.

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

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

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

- вложения в акции не должны превышать 25% от всей суммы вкладываемых средств.

- вложения в сертификаты должны быть не менее 20% от всей суммы.

Выпишем уравнения, определяющие инвестиционные возможности в начале каждого года. Для 1-го года:

S1 + B1 + С1 + I1 = 1000000 руб.

Во 2-м году распределяются средства I1, оставшиеся неинвестированными с начала 1-го года (других средств в этот момент нет):

S2 + B2 + I2 = I1

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

S3 + B3 + I3 = I2 + 1,3 S1

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

S4 + D4 + I4 = I3 + 1,3 S2 + 1,5 B1

В начале 5-го года возвратятся также средства, вложенные в сертификаты в начале 1-го года, и средства, лежащие на депозитах с начала 4-го года. Вложение же средств в начале 5-го года возможно только в депозиты:

D5 + I5 = I4 + 1,3 S3 + 1,5 B2 + 1,7 С1 + 1,2 D4

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

Z =    Þ  max

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

    £    0,25  (  +   + C1  + )

   C1     ³    0,20  ( +   + C1  +  )

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

Условия неотрицательности вложений:

S1,...S4  ³  0,   B1,...B3  ³  0,   C1 ³ 0,   D4, D5  ³  0,   I1,...I5  ³  0.

Задача формулируется следующим образом:

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

Выпишем задачу полностью:

Z =   Þ  max

при условиях:

 

S1 + B1 + С1 + I1 = 1000000

S2 + B2 + I2 = I1

S3 + B3 + I3 = I2 + 1,3 S1

S4 + D4 + I4 = I3 + 1,3 S2 + 1,5 B1

D5 + I5 = I4 + 1,3 S3 + 1,5 B2 + 1,7 С1 + 1,2 D4

  £   0,25 ( +  + C1  + )

    C1   ³   0,20 ( +  + C1  +  )

S1,...S4  ³  0,   B1,...B3  ³  0,   C1 ³ 0,   D4, D5  ³  0,   I1,...I5  ³  0.

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

S1 + B1 + I1 + С1= 1000000

S2 + B2 - I1 + I2 = 0

-1,3 S1 + S3 + B3 - I2 + I3 = 0

-1,3 S2 + S4 - 1,5 B1 + D4 - I3 + I4 = 0

-1,3 S3 - 1,5 B2 - 1,7 С1 + 1,2 D4 + D5 - I4 + I5 = 0

Аналогично поступим и с условиями на диверсификацию.

0,75 -  0,25 -  0,25 C1  -  0,25   £   0

       -0,20 -  0,20 + 0,80 C1  -  0,20   ³   0

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

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

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

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

S1 = X1,  S2 = X2,  S3 = X3,  S4 = X4,  B1 = X5,  B2 = X6, ...

… I5 = X15   - всего 15 переменных.

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