🗊Презентация Задачи о распределении ресурсов

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

Линейное программирование Характерные черты задач линейного программирования: 1) показатель оптимальности представляет собой линейную функцию от элементов решения X =(x1,x2,...,xn); 2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств

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

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

Пример 1 Фирма выпускает три вида изделий. В процессе производства используются три технологические операции. Затраты времени на каждую операцию для каждого изделия указаны на технологической схеме. Фонд рабочего времени ограничен следующими предельными значениями: для 1 операции – 430 мин, для 2 операции – 460 мин, для 3 операции – 420 мин. Ожидаемая прибыль от продажи одного изделия видов 1, 2 и 3 составляет 3, 2 и 5 ден. ед. соответственно. Определить наиболее выгодный суточный объем производства каждого вида продукции.

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

Построение математической модели задачи Что является искомыми величинами задачи? Искомые величины являются переменными задачи: х1 – объем производства изделия 1, х2 – объем производства изделия 2, х3 – объем производства изделия 3. Какова цель решения? Какой параметр задачи служит критерием эффективности (оптимальности) решения? В каком направлении должно изменяться значение этого параметра (к max или к min)? Цель решения записывается в виде целевой функции

Построение математической модели задачи Цель решения – максимизация прибыли. Целевая функция: Z(x) = 3х1+2х2+5х3 → max Какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены? Условия, налагаемые на переменные и ресурсы задачи, записываются в виде системы ограничений. Возможные объемы х1, х2 и х3 ограничиваются фондом рабочего времени по каждой операции: использование фонда рабочего времени на операции 1(мин): 1х1+2х2+1х3≤430; использование фонда рабочего времени на операции 2(мин): 3х1+2х3≤460; использование фонда рабочего времени на операции 3(мин): 1х1+4х2≤420; объемы производства компьютеров не могут быть отрицательными х1≥0, х2 ≥0, х3≥0

Модель задачи Z(x) = 3х1+2х2+5х3 → max 1х1+2х2+1х3≤430 3х1+2х3≤460 1х1+4х2≤420 х1≥0, х2 ≥0, х3≥0

Задачи анализа чувствительности оптимального решения 1. Анализ сокращения или увеличения ресурсов: • на сколько можно увеличить запас дефицитного ресурса для улучшения оптимального значения целевой функции? • на сколько можно уменьшить запас недефицитного ресурса при сохранении оптимального значения целевой функции? 2. Увеличение запаса какого из ресурсов наиболее выгодно? 3. Анализ изменения коэффициентов целевой функции: каков диапазон изменения коэффициентов целевой функции, при котором не меняется оптимальное решение?

Отчет по результатам

Отчет по устойчивости

Результирующее значение - оптимальные значения переменных решения. Результирующее значение - оптимальные значения переменных решения. Нормированная стоимость показывает, на сколько изменится значение целевой функции в случае принудительного включения единицы этой продукции в оптимальное решение. Например, нормированная стоимость для изделия 1 равна -4. Это означает, что если мы, несмотря на оптимальное решение, потребуем включить в план выпуска еще одно изделие 1, то новый план выпуска принесет нам прибыль 2150-4=2146 руб./день, что на 4 руб. меньше, чем в прежнем оптимальном решении. Коэффициенты ЦФ.

Предельные значения приращения целевых коэффициентов, при которых сохраняется первоначальное оптимальное решение (допустимое увеличение, допустимое уменьшение). Предельные значения приращения целевых коэффициентов, при которых сохраняется первоначальное оптимальное решение (допустимое увеличение, допустимое уменьшение). Например, допустимое увеличение прибыли от реализации изделия равно 4 ден.ед./шт., а допустимое уменьшение – практически не ограничено. Это означает, что если прибыль от реализации изделия 1 возрастет более чем на 4 ден. ед./шт (станет равной 7 ден.ед./шт.), то оптимальное решение изменится: станет целесообразным выпуск изделия 1. А если она будет снижаться вплоть до нуля, то оптимальное решение останется прежним.

Двойственная задача