Постановка задачи исследования как задачи линейного

Программирования.

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

Рассмотрим следующие задачи:

Задача №1.

Постановка задачи.

Перед зданием вокзала можно оборудовать

- киоски (не более пяти, но не менее одного)

- места автостоянок (не меньше десяти, но не более пятидесяти).

- пункты питания (не меньше одного, но не более трех).

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

Исходные данные задачи №1.

Таблица 1

Объекты   Расходы на содержание (д.е.) Прибыль (д.е.) Затраты на установку (д.е.) Ограничения по кол-ву объектов
Киоски (Х1) 0,2 2,0 1 Постановка задачи исследования как задачи линейного - student2.ru Х1 Постановка задачи исследования как задачи линейного - student2.ru 5
Автостоянки (Х2) 0,1 0,3 0,5 10 Постановка задачи исследования как задачи линейного - student2.ru Х2 Постановка задачи исследования как задачи линейного - student2.ru 50
Пункты питания (Х3) 2,0 5,0 1 Постановка задачи исследования как задачи линейного - student2.ru Х3 Постановка задачи исследования как задачи линейного - student2.ru 3

Математическое описание задачи.

Z = 2Х1+0.3Х2+5Х3 Постановка задачи исследования как задачи линейного - student2.ru max – целевая функция (максимум прибыли)

Ограничение по расходам на эксплуатацию:

0,2Х2+0,1Х3+2Х3 Постановка задачи исследования как задачи линейного - student2.ru 6

Ограничение по затратам на оборудование:

1+0,5Х2+1,5Х3 Постановка задачи исследования как задачи линейного - student2.ru 45

Ограничения по количеству объектов:

Постановка задачи исследования как задачи линейного - student2.ru

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

Задача №2.

Постановка задачи.

Предприятие «Пассажиравтотранс» выполняет пассажирские перевозки (см. табл 2). Разработать план работы предприятия, обеспечивающий максимальную прибыль.

Исходные данные задачи №2

Таблица 2

Виды пассажирских перевозок Затраты на 1 м.ч., руб Доход на 1 м.ч., руб Прибыль на 1 м.ч., руб Накат м. часов
Городские с льготами (X1) 900 Постановка задачи исследования как задачи линейного - student2.ru X1 Постановка задачи исследования как задачи линейного - student2.ru 4000
Городские без льгот (X2) 900 Постановка задачи исследования как задачи линейного - student2.ru X2 Постановка задачи исследования как задачи линейного - student2.ru 3800
Пригородные с льготами (X3) 900 Постановка задачи исследования как задачи линейного - student2.ru X3 Постановка задачи исследования как задачи линейного - student2.ru 3700
Пригородные без льгот (X4) 900 Постановка задачи исследования как задачи линейного - student2.ru X4 Постановка задачи исследования как задачи линейного - student2.ru 3200
Маршрутное такси городское (X5) 900 Постановка задачи исследования как задачи линейного - student2.ru X5 Постановка задачи исследования как задачи линейного - student2.ru 2800
Маршрутное такси пригородное (X6) 900 Постановка задачи исследования как задачи линейного - student2.ru X6 Постановка задачи исследования как задачи линейного - student2.ru 2500
Заказное (X7) 900 Постановка задачи исследования как задачи линейного - student2.ru X7 Постановка задачи исследования как задачи линейного - student2.ru 2200
Междугородние (X8) 900 Постановка задачи исследования как задачи линейного - student2.ru X8 Постановка задачи исследования как задачи линейного - student2.ru 2200
Международные (X9) 900 Постановка задачи исследования как задачи линейного - student2.ru X9 Постановка задачи исследования как задачи линейного - student2.ru 2200

Математическое описание задачи.

Целевая функция (максимум прибыли):

Z =40X1+100X2+110X3+140X4+190X5+290X6+300X7+320X8+

+350X9 Постановка задачи исследования как задачи линейного - student2.ru max

Ограничения по затратам:

310X1+310X2+310X3+310X4+310X5+310X6+310X7+310X8+

+310X9 Постановка задачи исследования как задачи линейного - student2.ru 2 511 000

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

35X1+410X2+400X3+450X4+500X5+600X6+610X7+630X8+

+660X9 Постановка задачи исследования как задачи линейного - student2.ru 2 511 000

Ограничения по накату:

900 Постановка задачи исследования как задачи линейного - student2.ru X1 Постановка задачи исследования как задачи линейного - student2.ru 4000
900 Постановка задачи исследования как задачи линейного - student2.ru X2 Постановка задачи исследования как задачи линейного - student2.ru 3800
900 Постановка задачи исследования как задачи линейного - student2.ru X3 Постановка задачи исследования как задачи линейного - student2.ru 3700
900 Постановка задачи исследования как задачи линейного - student2.ru X4 Постановка задачи исследования как задачи линейного - student2.ru 3200
900 Постановка задачи исследования как задачи линейного - student2.ru X5 Постановка задачи исследования как задачи линейного - student2.ru 2800
900 Постановка задачи исследования как задачи линейного - student2.ru X6 Постановка задачи исследования как задачи линейного - student2.ru 2500
900 Постановка задачи исследования как задачи линейного - student2.ru X7 Постановка задачи исследования как задачи линейного - student2.ru 2200
900 Постановка задачи исследования как задачи линейного - student2.ru X8 Постановка задачи исследования как задачи линейного - student2.ru 2200
900 Постановка задачи исследования как задачи линейного - student2.ru X9 Постановка задачи исследования как задачи линейного - student2.ru 2200
Постановка задачи исследования как задачи линейного - student2.ru Постановка задачи исследования как задачи линейного - student2.ru Постановка задачи исследования как задачи линейного - student2.ru

Выработка альтернативных вариантов решения в

Диалоге с ЭВМ.

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

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

Для выработки альтернативных вариантов можно менять :

– ограничения

– целевую функцию

– величину ограничений*

– значения коэффициентов уравнений.

Замена целевой функции означает смену цели проекта. Например, целью может быть:

– максимум прибыли,

– минимум расходов на содержание,

– минимум затрат на установку или минимум объема перевозок и пр.

Это позволит посмотреть на проект с разных точек зрения.

Замена величины ограничений означает изменение условий проекта, на которые ЛПР** согласен. Это может быть увеличение ( уменьшение) затрат на установку, на содержание и ремонт, на накат и т.д.

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

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

Рассмотрим альтернативные варианты решения задачи №2 (см. табл. 3).

Варианты плана пассажирских перевозок предприятия

“Пассажиравтотранс”.

Таблица 3

прибыль (тыс. руб) затраты тыс. руб) Рентабельность = Постановка задачи исследования как задачи линейного - student2.ru Оптимальное решение варианта
п/п X1 X2 X3 X4 X5 X6 X7 X8 X9
0,6594
0,766
0,7646
0,7058
0,6231
0,5804
0,85066    
0,8184    
0,7097    
0,98606        
0,51374
0,8704
0,8862

Замечания:

В этих вариантах изменялись не только величина ограничений по затратам, но и ограничения по накату часов. А именно:

- В варианте 7 нижний предел для X1 и X2 равен 0.

- В варианте 8 X2=X4=0

- В варианте 9 X2=X4=0; X6=X7=X8=X9=900.

- В варианте 10 нижний предел для X1,X2,X3,X4 равен 0.

- в варианте 11 X5=X6=X7=X8=X9=900.

- в варианте 12 верхний предел для X5,X6,X7,X8,X9 равен 5000.

На 1 этапе исследования рассматривается состояние предприятия при условии изменения затрат (см. варианты 1,2,3,4,5,6. Таб.3, рис.2).

Постановка задачи исследования как задачи линейного - student2.ru прибыль

Постановка задачи исследования как задачи линейного - student2.ru

Постановка задачи исследования как задачи линейного - student2.ru 1000 2000 3000 4000 5000 6000 7000 8000 9000 затраты

Рис.2 Зависимость прибыли от затрат в проекте пассажирских перевозок.

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

На 2 этапе исследования рассматривалось, как будет меняться состояние предприятия при одних и тех же максимальных затратах и меняющихся ограничениях на различные виды пассажирских перевозок (см.Таб.3, варианты 7,8,9,10).

Анализ этих вариантов показал, что они высокорентабельны. Наиболее экономичным является вариант 10. Однако, он предусматривает отказ от общественного транспорта. Следующим по экономичности является вариант 7. Он предполагает сохранение общественного транспорта без льгот. Даже 8 вариант (менее экономичный, чем 10 и 7), предусматривающий наличие перевозок общественным транспортом со льготами, прибыльнее варианта 1, и рентабельнее всех вариантов 1 этапа.

На 3 этапе исследовался вариант плана перевозок, предусматривающий увеличение затрат и ограничения на коммерческие виды перевозок (см. Таб.3 вариант 11). Вариант оказался самым нерентабельным.

На 4 этапе исследовались варианты плана, предполагающие увеличение затрат и верхних границ для коммерческих видов перевозок (см. Таб.3 варианты 12,13). Эти варианты высоко рентабельны и прибыльны. Они предусматривают к тому же сохранение общественных видов транспорта. Их можно рекомендовать. Однако, окончательный выбор варианта осуществляет ЛПР.

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

* Рекомендация:

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

** ЛПР – лицо, принимающее решение

Наши рекомендации