Задача о распределении средств между предприятиями — КиберПедия 

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

Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...

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

2017-09-27 1260
Задача о распределении средств между предприятиями 0.00 из 5.00 0 оценок
Заказать работу

Рассмотрим схему решения задач динамического программирования с использованием уравнений Беллмана на примере задачи о распределении средств между предприятиями.

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

Планируется деятельность трех предприятий на очередной год. Начальные средства s0, которые следует распределить, составляют 5 усл. ед. Размеры вложения в каждое предприятие кратны 1 усл. ед. Средства x, выделенные предприятию k, приносят в конце года прибыль Функции заданы таблично (табл. 1). При решении подобных задач принято считать, что выполняются следующие предположения:

– прибыль предприятия k не зависит от вложения средств в другие предприятия;

– прибыль выражается в одних условных единицах;

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

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

Таблица 1

Эффективность использования средств

x f1(x) f2(x) f3(x)
       
       
       
       
       

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

(14)

Переменные xk удовлетворяют следующим ограничениям:

(15)

Требуется найти переменные x1, x2, x3, удовлетворяющие системе ограничений (15), при которых функция (14) достигает максимума.

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

Процесс распределения средств можно рассматривать как трехшаговый, номер шага совпадает с номером предприятия. Выбор переменных x1, x2, x3 – это выбор управления соответственно на 1, 2 и 3 шаге. Конечное состояние процесса распределения , когда все средства вложены в производство.

Графически схема распределения показана на рис. 9.

Рис.9. Схема распределения средств
Z1*(s0)
Z3*(s2)
Z2*(s1)
s0=5

Уравнения состояний имеют вид:

(16)

где sk – параметр состояния, количество средств, оставшихся после k -го шага, т. е. эти средства остается распределить между (3 – k) оставшимися предприятиями.

Рассмотрим функцию – условную оптимальную прибыль, полученную от предприятий k, (k + 1), …, 3, если между ними оптимальным образом распределялись средства . Допустимые управления на шаге k удовлетворяют условию: .

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

(17)

Последовательно решаем уравнения, проводя условную оптимизацию каждого шага.

Решение задачи.

Шаг k=3. В табл. 1 прибыль монотонно возрастает, поэтому все средства, оставшиеся к третьему шагу, следует вложить в предприятие 3 (рис.10).

Z3*(s2)=f3(s2)
Рис.10. Распределение средств на шаге 3

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

(18)

Шаг k=2. Делаем все предположения относительно остатка средств ко второму шагу, т. е. после выбора значения величина может принимать значения 0, 1, 2, 3, 4, 5. В зависимости от этого выбираем , находим и сравниваем для разных при фиксированном значения суммы .

Z3*(s2)
Рис.11. Распределение средств на шаге 2

Для каждого наибольшее из этих значений – это условная оптимальная прибыль, получаемая при оптимальном распределении средств между 2-м и 3-м предприятиями (рис.11).

Вычисления записаны в таблице 2. Для каждого значения оптимальные значения и записаны в графах 5 и 6.

Таблица 2

Оптимизация распределения средств при k=2

s1 x2 s2
           
      0+4=4    
    6+0=6    
      0+8=8    
    6+4=10    
    9+0=9    
      0+12=12    
    6+8=14    
    9+4=13    
    12+0=12    
      0+16=16    
    6+12=18    
    9+8=17    
    12+4=16    
    15+0=15    
      0+20=20    
    6+16=22    
    9+12=21    
    12+8=20    
    15+4=19    
    18+0=18    

Шаг k=1. Графическое представление шага представлено на рисунке 12. Условная оптимизация проведена в таблице 3.

Z3*(s2)
Z2*(s1)
s0=5
Рис.12. Распределение средств на шаге 1

Например, если , то . Прибыль, полученная от трех предприятий при условии, что 5 единиц средств будут распределены оптимально между оставшимися двумя предприятиями, равна . Значение взято из столбца 5 табл. 2 при . Если , то . Суммарная прибыль при условии оптимального распределения средств равна . Значение взято из исходных данных (табл. 1), значение – из столбца 5 табл. 2 при . Аналогично вычислены остальные значения столбца 4 табл. 3.

Таблица 3

Оптимизация распределения средств при k=1

s0 x1 s1
      0+22=22    
    8+18=26    
    10+14=24    
    12+10=22    
    14+6=20    
    16+0=16    

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

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


Поделиться с друзьями:

Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...

Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...

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

Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.013 с.