Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информационные технологии и моделирование бизнес-процессов

Задача о строительстве и эксплуатации предприятий

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

Запишем математическую модель задачи. Для этого введем величины:

Тогда математическая модель задачи будет такой:

где С выражает суммарные затраты на строительство и эксплуатацию предприятий.

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

Процесс решения задачи разобьем на т шагов. На первом этапе определяем минимальные затраты при размещении в первом регионе

Оптимальный план размещения и предприятий среди m регионов определяется следующим образом. Пусть

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

Пусть gi (xj) (i = 1,2,3) - затраты на строительство и эксплуатацию xj = j (j = 0,1, ..., 5) предприятий, расположенных в i-м регионе. Надо так распределить строительство предприятий между тремя регионами, чтобы обеспечить минимум затрат на их строительство и эксплуатацию. Задачу решить на основе данных таблицы 8.5.

Таблица 8.5. Расходы на строительство и эксплуатацию предприятий

Расходы на строительство и эксплуатацию предприятий

Процесс решения данной задачи разобьем на три шага. На первом этапе определим минимальные затраты при размещении в первом регионе

регионах. И, наконец, на третьем этапе определим минимальные затраты при размещении пяти предприятий в трех регионах. На первом этапе

Таблица 8.6. Расходы на строительство и эксплуатацию предприятий

Расходы на строительство и эксплуатацию предприятий

Расходы на строительство и эксплуатацию предприятий

С табл.8.6. видим, что F2 * (0) = 0, F2 * (1) = 15 F2 * (2) = 20 F2 * (3) = 25, F2 * (4) = 40, F2 * (5) = 55 .

Далее достаточно вычислить F3 (5). Получим таблицу 8.7.

Таблица 8.7. Расходы F3 (5)

Расходы F3 (5)

С табл.8.7 видим, что F3 * (5) = 50.

Оптимальный план размещения пяти предприятий между тремя регионами определяется так.

Поскольку F3 * (5) = 50 и достигается для k = 1, то в третий регион надо разместить одно предприятие. Далее распределяем четыре предприятия между первыми двумя регионами. С табл.8.6 при х j = 4 имеем F2 * (4) = 40 и достигается для k = 3. Это означает, что три предприятия нужно разместить во втором регионе. Поэтому в первом регионе надо разместить одно предприятие.

Минимум затрат на строительство и эксплуатацию пяти предприятий составляет F3 * (5) = 50 ед.

Резюме

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

Чтобы для решения задачи можно было применять метод динамического программирования, должны выполняться два требования: состояние системы на отдельном этапе должен зависеть только от предыдущего состояния и управления на этом этапе (отсутствие последействия) функция цели должна быть аддитивной. Сформулированы требования лежат в основе принципа оптимальности Беллмана.

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

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

Ключевые слова

Динамическое программирование, принятия решений, оптимизация, принцип оптимальности Беллмана, управление, состояние системы, распределение ресурсов.

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

► Назовите необходимые условия применения метода динамического программирования к решению оптимизационных задач.

► Объясните свойство аддитивности функции цели.

► Проведите интерпретацию процесса получения водительских прав как многошагового.

► Приведите примеры задач (в общем виде), для решения которых лучше применять метод динамического программирования.

► Сформулируйте принцип оптимальности Беллмана.

 
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Естествознание
Журналистика
Инвестирование
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Математика, химия, физика
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Политэкономия
Право
Психология
Региональная экономика
Религиоведение
Риторика
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика
Прочее