- •Раздел 1 . Линейнное программирование
- •1. Вклад линейного программирования в решение управленческих задач. (постановка транспортной задачи, задачи распределения ресурсов)
- •2. Алгебраическая формулировка задачи линейного программирования
- •3.Канонические формы для линейных оптимизационных моделей
- •4. Геометрическая интерпритация
- •5.Симплексный метод (решение задачи оптимального распределения ресурсов)
- •6. Анализ моделей на чувствительность и двойственная задача (на примере задачи оптимального распределения ресурсов)
- •Теорема двойственности
- •Следствие теоремы двойственности (Теорема о дополнительной нежесткости)
- •Решение двойственной задачи на примере задачи распределения ресурсов
- •8 Реализация задач линейного программирования средствами ms Excel Реализация задачи распределения ресурсов посредством ms Excel.
- •Анализ оптимального решения
- •Алгоритм решение транспортной задачи с помощью ms Excel.
- •Раздел 2 . Нелинейное программирование
- •1. Вклад нелинейного программирования в решение управленческих задач.
- •2. Общая формулировка и классификация задач нелинейного программирования
- •Классификация методов нелинейного программирования
- •1.Классификация по некоторым аспектам постановки задачи.
- •2. Классификация по характерным чертам методов решения.
- •3.Классификация по методам компьютерной реализации.
- •3. Гиперболическое ( дробно-линейное) программирование
- •4. Постановка и решение задачи о снижении себестоимости продукции
- •3.Решение задач нелинейного программирования средствами ms Excel
- •1. Ввод данных для задачи нелинейного программирования
- •Раздел 3. Динамическое программирование
- •1. Вклад динамического программирования в решение управленческих задач (постановка задачи о замене оборудования, оптимального распределения инвестиций, о строительстве и оснащении )
- •2.Общая постановка задачи динамического программирования. Принцип оптимальности Беллмана.
- •3.Решение задач динамического программирования (методом оптимальности Беллмана)
6. Анализ моделей на чувствительность и двойственная задача (на примере задачи оптимального распределения ресурсов)
При решении управленческих задач методами линейного программирования нельзя довольствоваться лишь численными значениями управляемых переменных, при которых достигается оптимум, если рассматриваемая задача не применялась многократно и диапазон ее возможностей заранее не известен.
Следует определить интервал допустимых изменений входных параметров при которых отклонение от найденного оптимального решения незначительно, т.е. необходимо знать насколько чувствительным оказывается полученное решение к выбору исходных данных.
На многие вопросы, связанные с анализом на чувствительность, легко ответить, располагая численными данными на заключительной симплекс -итерации. К числу таких вопросов относятся, в частности, следующие:
Останется ли решение оптимальным, если уменьшится удельный вклад в прибыль одной из базисных переменных?
К каким последствиям приведет сокращение объема ресурсов?
Что произойдет, если ввести в рассмотрение новую управляемую переменную?
В теории линейного программирования существует понятие двойственности, которое позволяет унифицированным образом устанавливать взаимосвязи для всех приемов и методов анализа на чувствительность.
Исходная и двойственная задачи.
Рассмотрим две следующие задачи линейного программирования:
n
максимизировать cj xj (1)
j=1
при наличии ограничений
n
a ij x j <= b i (i=1,2, ... , m), (2)
j=1
xj >= 0 (j=1,2, ... , n). (3)
и
m
минимизировать bi yi (4)
i=1
при ограничениях
n
a ij yi >= cj ( i=1,2, ... , n), (5)
j=1
yi >= 0 ( i=1,2, ... , m ). (6)
В теории линейного программирования первую задачу [ cоотношения (1)-(3)] называют исходной , а вторую [соотношения (4)-(6)] двойственной по отношению к первой.
Двойственная задача - это на 90 градусов повернутая исходная задача. Верны утверждения:
1. j-й столбец, составленный из коэффициентов, фигурирующих в ограничениях исходной модели, совпадает с j-ой строкой, составленной из коэффициентов, фигурирующих в ограничениях двойственной модели;
2. строка, составленная из коэффициентов в выражении для целевой функции, совпадает со столбцом, составленным из констант, фигурирующих в правых частях ограничений двойственной модели;
3. столбец, составленный из констант, фигурирующих в правых частях ограничений исходной модели, совпадает со строкой, составленной из коэффициентов в выражении для целевой функции двойственной модели;
4. направление знаков неравенства в исходной модели противоположно направлению знаков неравенства в двойственной модели; требование максимизации в исходной задачи в двойственной заменено требованием минимизации.
Пример:
исходная задача:
максимизировать: 4 x1 + 5x2 + 9x3 (7)
при следующих ограничениях:
1x1 + 1x2 + 2x3 <=16
7x1 + 5x2 + 3x3<=25 (8)
x1>=0, x2>=0, x3>=0
двойственная задача:
минимизировать: 16y1 + 25y2 (9)
при следующих ограничениях:
1y1 + 7y2 >=4,
1y1 + 5y2>=5, (10)
2y1 + 3y2 >=9,
y1 >=0, y2>=0.