- •Mатематика, ч.2 методы оптимизации
- •1. Информация о дисциплине
- •1.1. Предисловие
- •1.2. Содержание дисциплины и виды учебной работы
- •1.2.1. Объем дисциплины и виды учебной работы
- •1.2.2. Перечень видов практических занятий и контроля:
- •2.2.2. Тематический план дисциплины
- •2.2.3. Тематический план дисциплины
- •2.3. Структурно-логическая схема дисциплины
- •2.4. Временной график изучения дисциплины
- •2.5. Практический блок
- •2.5.1. Практические занятия
- •2.5.1.1. Практические занятия (очная/очно-заочная формы обучения)
- •2.5.1.2. Практические занятия (заочная формы обучения)
- •2.5.2. Лабораторные работы (для всех форм обучения)
- •Балльно-рейтинговая система
- •3. Информационные ресурсы дисциплины
- •3.1. Библиографический список
- •3.2. Опорный конспект лекций введение
- •Раздел 1. Линейное программирование. Основные понятия
- •Стандартная и каноническая формы задачи линейного программирования
- •Пример 1.1.1
- •Пример 1.1.2
- •Пример 1.1.3
- •1.2. Двойственная задача
- •Пример 1.2.1
- •1.3. Базисные решения.
- •Пример 1.3.1
- •Раздел 2. Решение прямой задачи линейного программирования симплекс-методом
- •2.1. Теоремы двойственности. Алгоритм симплекс-метода
- •Пример 2.1.1
- •2.2. Анализ оптимальной симплекс-таблицы
- •2.3. Интервалы устойчивости. Ценность ресурсов
- •Пример 2.3.1
- •Пример 2.3.2
- •Пример 2.3.3
- •Раздел 3. Решение транспортной задачи. Матричные игры
- •3.1. Математическая постановка транспортной задачи
- •Пример 3.1.1
- •3.2. Матричные игры. Основные понятия
- •Пример 3.2.1
- •3.3. Решение матричных игр в смешанных стратегиях
- •Пример 3.3.1
- •3.4. Решение матричных игр симплекс-методом
- •Пример 4.3.1
- •Раздел 4. Целочисленное и нелинейное программирование
- •4.1. Задача о назначениях
- •Пример 4.1.1
- •4.2. Нелинейное программирование
- •Пример 4.2.1
- •Раздел 5. Производственные функции
- •5.1. Свойства производственных функций
- •Примеры производственных функций.
- •Пример 5.1.1
- •Пример 5.1.2
- •Пример 5.1.3
- •Пример 5.1.4
- •Пример 5.1.5
- •5.2. Характеристики производственных функций
- •Пример 5.2.1
- •Пример 5.2.2
- •Пример 5.2.3
- •5.3. Модель фирмы
- •Пример 5.3.1
- •Геометрическая иллюстрация оптимального решения
- •5.4. Функции спроса на ресурсы и функция предложения продукции
- •Пример 5.4.1
- •Вопросы для самопроверки
- •Раздел 6. Модели потребителького спроса
- •6.1. Функции полезности
- •2. Неоклассическая мультипликативная функция
- •3. Логарифмическая функция
- •Пример 6.1.1
- •Пример 6.1.2
- •Пример 6.1.3
- •6.2. Кривые безразличия
- •Пример 6.2.1
- •Пример 6.2.2
- •Пример 6.2.3
- •Вопросы для самопроверки
- •6.3. Задача потребительского выбора
- •Пример 6.3.1
- •Пример 6.3.2
- •Вопросы для самопроверки
- •6.4. Влияние на спрос цен товаров и дохода потребителя.
- •Пример 6.4.1
- •Пример 6.4.2
- •Вопросы для самопроверки
- •6.5. Уравнение Слуцкого
- •Пример 6.5.3
- •3.3. Технические и программные средства обеспечения дисциплины
- •Порядок выполнения работы
- •3.1. Выполнение задания 1
- •Пример 1.1.1
- •Решение
- •3.3.1. Построение начального базисного плана
- •3.2. Выполнение задания 2
- •Работа 2. Решение транспортной задачи и матричной игры
- •1. Цель работы
- •2. Основные теоретические положения
- •Порядок выполнения работы
- •3.1. Выполнение задания 1
- •Решение
- •3.1.1. Заполнение исходных данных
- •3.2. Выполнение задания 2 Пример
- •Решение
- •3.5. Глоссарий
- •4. Блок контроля освоения дисциплины
- •4.1. Методические указания к выполнению контрольной работы
- •4.1.1. Задание на контрольную работу
- •Варианты заданий 1 и 2
- •Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •4.1.2. Методические указания к выполнению контрольной работы Пример задания 1
- •Записать стандартную и каноническую формы
- •Графическое решение задачи
- •Пример задания 2. Двойственная задача
- •Найти оптимальное решение двойственной задачи
- •Пример задания 3
- •Решение
- •Пример задания 4
- •1. Вычислим равновесный спрос при заданных ценах и доходе
- •4.2. Тесты текущего контроля (по разделам) Тест № 1
- •Тест № 2
- •Тест № 3
- •Тест № 4
- •Тест № 5
- •Тест № 6
- •4.3. Итоговый тест
- •4.4. Вопросы к экзамену
- •Содержание
2.2. Анализ оптимальной симплекс-таблицы
Значения во втором столбце определяют значения базисных переменных x1=100,x2=50. Все переменные, не входящие в первый столбец, являются свободными и поэтому равны 0:s1=0,s2=0.
Таким образом, в оптимальном решении:
первый продукт производится в количестве 100 единиц (x1=100);
второй продукт производится в количестве 50 единиц (x2 = 50);
оба ресурса используются в производстве полностью (s1 =s2 = 0).
Таким образом, в оптимальном решении прямой задачи
X* = {x1 = 100,x2 = 50,s1 = 0,s2= 0}
значения в последней строке симплекс-таблицы определяют соответственно:
значение целевой функциипрямой задачиZ = 9 000(выручка от реалии-зации продукции составляет 9 000 у.е.);
значения 0 в столбцах x1 и x2 означают, что производства первого и второго продуктов рентабельны:Δ1=0, Δ2=0;
значение 4 в столбце s1 означает, что теневая цена 1 кг сырья равна 4 у.е:y1=4;
значение 200 в столбце s2 означает, что теневая цена работы 1 часа оборудования равна 200 у.е.:y2=200;
значение целевой функциидвойственной задачи:
W= 1 000y1 + 25y2= 1 000 ∙4+25∙200 = 9 000 (=Z).
Таким образом, оптимальное решение двойственной задачи:
Y* = {y1=4,y2=200, Δ1 =0, Δ2=0 }.
Вопросы для самопроверки
В чем состоит критерий оптимальности?
Как определяется ведущая строка?
Как заполняется последняя строка симплекс-таблицы?
Какой элемент симплекс-таблицы содержит значение выручки?
Как находятся значения базисных переменных из симплекс-таблицы?
Как находятся значения свободных переменных из симплекс-таблицы?
Как находятся значения двойственных переменных из симплекс-таблицы?
2.3. Интервалы устойчивости. Ценность ресурсов
Изучаемые вопросы:
Свойства оптимальных решений;
Двойственная переменная как ценность ресурсов;
Определение оптимального плана;
Определение границ интервала устойчивости.
Рассмотрим влияние запасов ресурсов на оптимальное решение прямой задачи.
Допустим, что запас ресурса kизменился на величину Δbk, а запасы осталь-ных ресурсов не изменяются.
Определение. Интервал [] называется интервалом устойчивости, если для любого запаса ресурсаkиз этого интервала выполняются условия:
состав оптимальных базисных переменных прямой и двойственной задач не изменяется;
оптимальные теневые цены всех ресурсов не изменяются.
Величины ,называются соответственномаксимально допустимым уменьшением и увеличением ресурса k. Таким образом, интервал устойчивости будет равен
.
Изменение запаса ресурса вызывает изменение выручки и оптимального плана выпуска продукции. Из определения интервала устойчивости следует, что структура производственной программы не изменяется при изменении запаса ресурса, т. е. новая производственная программа рекомендует выпускать те же виды продукции, но в других количествах. Математически это означает, что список оптимальных базисных переменных не изменяется при изменении запаса ресурса в интервале устойчивости.
Следующая теорема показывает изменение выручки Zв зависимости от изменения запаса ресурса.
Теорема об оценке. Допустим, что запас ресурсаkизменился на величину Δbkтак, что новый запас этого ресурса равенbk + Δbk, лежит в интервале устойчивости. Тогда выручка изменится на величину
Z = yk Δ bk .
Если допустимо изменение ресурса на 1, т.е. Δ bk = 1, то из равенстваZ=yk следует, что теневая ценаykпоказывает изменение выручкиZ,выз-ванное изменением запаса этого ресурса на 1, т.е. определяет ценность этого ресурса для производства. Из теоремы равновесия следует, что теневая цена недефицитного ресурса равна 0. Тогда изменение избыточного ресурса не изменяет величину выручки, т.е. его ценность равна 0.
Найдем изменения оптимального плана, вызванные изменением запаса ресурса k. Заметим, что второй столбец оптимальной симплекс-таблицы определяет объемы производств исходной задачи. Изменение запаса ресурса вызывает изменения в этом столбце по следующему правилу: к их прежним значениям (элементам второго столбца) прибавляются соответствующие элементы столбца переменной xk+n, умноженные на величину изменения запаса ресурса Δ bk. При этом все небазисные переменные остаются равными 0.Максимально допустимые уменьшения и увеличения ресурса и интервал устойчивости можно найти из полученного оптимального плана.