Задача распределения ресурсов онлайн

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

Пример №1 . Планируется работа двух предприятий на n лет. Начальные ресурсы равны s0. Средства x, вложенные в 1-е предприятие в начале года, дают в конце года прибыль f1(x), и возвращаются в размере g1(x). Средства y, вложенные в 2-е предприятие в начале года, дают в конце года прибыль f2(y) и возвращаются в размере g2(y). В конце года возвращенные средства заново перераспределяются между отраслями. Определить оптимальный план распределения средств и найти максимальную прибыль.

Задачу решим методом динамического программирования. Операцию управления производственным процессом разобьём на этапы. На каждом из них управление выберем так, чтобы оно приводило к выигрышу как на данном этапе, так и на всех последующих до конца операции. В этом состоит принцип оптимальности, сформулированный американским математиком А. Беллманом.
Разобьём весь период на три этапа по годам и будем нумеровать их, начиная с первого.
Обозначим через x_k и y_k количество средств выделяемых каждому предприятию на k-ом этапе, а через x_k + y_k = a_k – общее количество средств на этом этапе. Тогда первое предприятие приносит на этом этапе 3 x_k, а второе 4 y_k единиц дохода. Общий доход на k-ом этапе 3x_k + 4y_k.
Обозначим через f_k (a_k) – максимальный доход, который получает отрасль от обоих предприятий на k-ом и всех последующих. Тогда функциональное уравнение, отражающее принцип оптимальности Беллмана, принимает вид:
f_k (a_k)=max<3x_k + 4y_k + f_k+1 (a_k+1)>. (1)
Так как x_k + y_k = a_k, то y_k = a_k — x_k и 3x_k + 4y_k = 3x_k + 4(a_k — x_k) = — x_k + 4a_k. Поэтому f_k(a_k) = max<-x_k + 4a_k + f_k+1(_ak+1)>. (2)
0 ≤ x_k ≤ a_k
Кроме того, ak – это средства выделяемые обои предприятиям на k-ом этапе, и они определяются остатком средств, получаемых на предыдущем (k-1)-ом этапе. Поэтому по условию задачи оптимальное управление на каждом этапе
a_k = 0,5x_k-1 + 0,2y_k-1 = 0,5x_k-1+0,2(a_k-1 — x_k-1) = 0,3x_k-1+0,2a_k-1. (3)

I.Условия оптимизации
Планирование начинаем с последнего третьего этапа

II. Безусловная оптимизация
Выясним, каким должно быть оптимальное управление процессом выделения средств между первым и вторым предприятиями для получения максимального дохода в количестве 4950 ден. ед.
1-й год. Так как x₁ = a₁ и , y₁ = 0, то все средства в количестве 900 ден. ед. отдаются первому предприятию.
2-й год. Выделяются средства a₂ = 0,3x₁ + 0,2a₁ = 0,5 a₁ =450 ед., x₂ = a₂ , y₂ = 0.
Все они передаются первому предприятию.
3-й год. Выделяются средства a₃ = 0,3x₂ + 0,2a₂ = 0,5 a₂ = 225 ед., x₃ = 0, y₃ = a₃ . Все они передаются второму предприятию.
Результаты решения представим в виде таблицы.

Задачи распределения ресурса на сетях

Рис. 7. Представление «операции-вершины» для сети рисунка 6

Для определения оптимального распределения ресурса необ-ходимо найти критические пути для каждого из вариантов распределения ресурса и сравнить длины этих путей (в сети, приведенной на рисунке 7, существует общий для операций «0-1» и «0-2» ресурс; потенциалы вершин, соответствующие различным способам использования этого ресурса — сначала выполняется операция «01», затем «0-2» и наоборот, приведены на рисунке 7 соответственно в квадратных скобках и без скобок).
Универсальных эффективных точных методов решения задач распределения ресурсов на сетях не существует. В качестве частного случая, для которого существует простой алгоритм, приведем следующий пример.
В сети, изображенной на рисунке 8, для трех операций известны поздние времена окончания ti. Требуется определить очередность выполнения этих трех операций при условии, что все операции выполняются одной единицей ресурса и поэтому не могут выполняться одновременно.

Рис. 8. Пример распределения ресурса

Легко показать, что в рассматриваемом примере оптимально выполнять первой операцию с минимальным ti.
Если для выполнения проекта выделено ограниченное количество ресурса, то возникает задача наилучшего его использования. Обозначим wi — объем i-ой операции, /-(у,) — скорость ее выполнения в зависимости от количества ресурса vПредположим, что /(•) — непрерывная справа неубывающая функция, причем /(0) = 0. Если vi(t) — количество ресурса на i-ой операции в момент времени
t, то момент ti ее окончания определяется как минимальное время, удовлетворяющее уравнению:
ti
/ (V (t ))dt = w,-.
0
Если количество ресурса, используемое при выполнении некоторой операции, не изменяется во времени, то говорят, что она выполняется с постоянной интенсивностью. Тогда продолжительность операции определяется выражением
ti(Vi) = wi //(v).
В настоящее время общих алгоритмов поиска распределения ограниченных ресурсов между операциями, минимизирующего время завершения проекта, не существует. Поэтому рассмотрим несколько частных случаев.
Пусть все операции независимы и выполняются ресурсом одного вида, количество которого равно R, а /(V,) — непрерывные строго монотонные вогнутые функции. Тогда существует оптимальное решение, в котором каждая операция выполняется с постоянной интенсивностью и все операции заканчиваются одновременно в момент времени T, определяемый как минимальное время, удовлетворяющее следующему неравенству:
n w
Z /»Чw) ? R,
i=1 T
где /_1Q — функция, обратная функции/(•), i = 1,n [7, 10].
Эвристические алгоритмы определения оптимального распределения ресурса для ряда случаев «невогнутых» функций интенсивности рассматриваются в [1-4].
Обширный класс задач КСПУ составляют задачи агрегирования — представления комплекса операций (проекта) в виде одной операции и исследования свойств таких представлений, для которых оптимизация в рамках агрегированного описания дает решение, оптимальное для исходного (детального) описания. Основные подходы к постановке и решению задач агрегирования рассматри-ваются в [1, 2, 10, 16].

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

От общей задачи линейного программирования — к частной

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

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

Система ограничений в задаче линейного программирования представляет собой систему линейных неравенств и (или) уравнений. Каждое неравенство или уравнение задаёт ограничение запасов одного из производственных факторов — вида сырья, времени, рабочей силы или чего-либо другого. Коэффициенты при неизвестных, записываемые обычно в виде буквы a с нижними индексами, обозначают количество производственного фактора, расходуемого для производства единицы соответствующего вида продукции. Это количество должно быть заранее известно.

Таким образом, система ограничений записывается в виде

Другой обязательный элемент модели задачи линейного программирования — функция цели. Как и система ограничений, она так же линейна. В функции цели присутствуют те же неизвестные, а коэффициенты при них, обычно записываемые в виде буквы c с нижними индексами, могут обозначать заранее известный доход от реализации единицы соответствующего вида продукции, а могут, как в задачах о расходе производственнных мощностей или в задаче о питании, обозначать расходы. Записывается функция цели в следующем виде:

.

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

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

Переменные в задаче использования ресурсов

Для изготовления двух видов продукции и требуется четыре вида ресурсов (сырья): , , , . Запасы сырья — соответственно , , , единицы.

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

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

Решение различных практических задач динамического программирования: Оптимальное распределение ресурсов

При пользовании «Инфоуроком» вам не нужно платить за интернет!

Минкомсвязь РФ: «Инфоурок» включен в перечень социально значимых ресурсов .

Учебная дисциплина МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В ЭКОНОМИКЕ

Тема урока Решение различных практических задач ДП с применением математических методов.

Развить навык решения задач динамического программирования.

Развитие качества ума, внимания, умений учебного труда студентов.

Воспитание дисциплинированности, целеустремленности студентов.

Оснащение урока конспект лекций, В.П.Агальцов «Математические методы в программировании».

проверка отсутствующих, заполнение журнала.

Актуализация опорных знаний: ответы на контрольные вопросы

Какие задачи называются многошаговыми?

При помощи какого математического аппарата решаются многошаговые задачи?

Что такое оптимальное управление u*?

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

Приведите примеры задач оптимального распределения ресурсов.

Изучение нового материала:

Классические задачи динамического программирования

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

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

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

Задача о вычислении чисел Фибоначчи

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

Задача о выборе траектории

Задача последовательного принятия решения

Задача об использовании рабочей силы

Задача управления запасами

Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.

Алгоритм Флойда — Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.

Алгоритм Беллмана — Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.

Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

Пример: Оптимальное распределение ресурсов

Капитал 40 млн.руб. инвестор должен вложить в четыре инвестиционных проекта так, чтобы получить максимальный доход. Доходность проектов дана в таблице (вложения кратны 8 млн. руб.)

Прибыль от внедрения

Это задача динамического программирования. Решение состоит из двух этапов. На первом этапе (от конца к началу) ищем условное оптимальное решение, на втором (от начала к концу) – ищем оптимальное решение задачи.

Распределяем капитал между четырьмя проектами и считаем получаемую прибыль L ( i ), i =8,16,24,32,40.

1 шаг: Денежные средства вкладываются в четвертый проект.

2 шаг: Денежные средства вкладываются в четвертый и третий проекты.

Прибыль от внедрения

3 шаг: Денежные средства вкладываются в четвертый, третий (2 шаг) и второй проекты.

Прибыль от внедрения

4 шаг: Денежные средства вкладываются в четвертый, третий, второй (3 шаг) и первый проекты.

Прибыль от внедрения

На четвертом шаге выбираем максимальное из полученных значений прибыли L (40)=214.

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

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

1 проект – 0 млн. руб.

2 проект – 24 млн. руб.

3 проект – 8 млн. руб.

4 проект – 8 млн. руб.

Закрепление нового материала:

5. Подведение итогов урока: выводы, оценки, домашнее задание:

Ср12: формирование и усвоение содержания теоретического материала

Выберите книгу со скидкой:

Математика. Экспресс-справочник для подготовки к ЕГЭ

350 руб. 107.00 руб.

ОГЭ. Математика. Большой сборник тематических заданий для подготовки к основному государственному экзамену

350 руб. 171.00 руб.

Для детского сада. Математика. Средняя группа

350 руб. 144.00 руб.

Математика. Сложение и вычитание. Уровень 3 Kumon

350 руб. 464.00 руб.

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

350 руб. 181.00 руб.

Математика. Вычитание. Уровень 2 Kumon

350 руб. 464.00 руб.

Математика. Дроби. Уровень 4 Kumon

350 руб. 464.00 руб.

Повтори летом! Математика. Полезные и увлекательные задания. 1 класс

350 руб. 87.00 руб.

Альбом по подготовке к школе. Математика

350 руб. 272.00 руб.

Для детского сада. Математика. Старшая группа

350 руб. 144.00 руб.

Для детского сада. Математика. Подготов. группа

350 руб. 144.00 руб.

Для детского сада. Математика. Младшая группа

350 руб. 144.00 руб.

БОЛЕЕ 58 000 КНИГ И ШИРОКИЙ ВЫБОР КАНЦТОВАРОВ! ИНФОЛАВКА

Инфолавка — книжный магазин для педагогов и родителей от проекта «Инфоурок»

Бесплатный
Дистанционный конкурс «Стоп коронавирус»

• Евдокимова Марина Дмитриевна
• Написать
• 0
• 30.10.2015

Номер материала: ДВ-109812

Добавляйте авторские материалы и получите призы от Инфоурок

Еженедельный призовой фонд 100 000 Р

«Развитие эмоционального интеллекта»

Спикер: Анна Быкова (#лениваямама)

• 30.10.2015
• 651

• 30.10.2015
• 538

• 30.10.2015
• 615

• 30.10.2015
• 670

• 30.10.2015
• 1241

• 30.10.2015
• 1452

• 30.10.2015
• 1869

Не нашли то что искали?

Как организовать дистанционное обучение во время карантина?

Помогает проект «Инфоурок»

Вам будут интересны эти курсы:

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение редакции может не совпадать с точкой зрения авторов.

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