- •Тема 1. Математическая модель задачи линейного программирования (злп)
- •1. Предмет математического программирования
- •2. Математическая модель мп
- •3. Основные типы задач мп:
- •4. Многокритериальная оптимизация
- •5. Основные понятия теории оптимизации
- •6. Постановка злп. Различные формы записи ее математической модели
- •Тема 2. Графический метод решения злп. Закономерности и общие свойства решения злп
- •1. Геометрическая интерпретация решения злп
- •2. Алгоритм решения злп графическим методом
- •3. Возможные случаи области допустимых решений при решении злп графическим методом:
- •4. Основные свойства решений злп:
- •5. Классификация решений злп
- •6. Решение злп с точки зрения линейной алгебры
- •Тема 3. Симплексный метод решения задач линейного программирования
- •1. Суть симплексного метода
- •2. Критерий оптимальности решения злп
- •3. Алгоритм основного симплекс-метода:
- •4. Алгоритм двойственного симплекс-метода:
- •5. Алгоритм смешанного симплекс-метода:
- •6. Особые случаи симплекс-метода:
- •Тема 4. Модифицированный симплекс-метод решения злп. Устойчивость оптимального решения злп
- •1. Обращенный базис и симплекс-множители
- •2. Модифицированный симплекс-метод
- •3. Устойчивость оптимального решения злп:
- •Тема 5. Двойственность в линейном программировании
- •1. Понятие двойственности и теневой цены
- •2. Правила построения двойственной злп
- •3. Основные теоремы двойственности и их экономическое содержание
- •Тема 6. Элементы теории матричных игр
- •1. Основные понятия
- •2. Теоремы теории игр для парных матричных игр с нулевой суммой
- •3. Способы решения задач ти:
- •Тема 7. Матричные статистические игры
- •1. Понятие статистической игры
- •2. Критерии выбора оптимальной стратегии при решении статистической игры
- •3. Кооперативные игры
- •Тема 8. Транспортная задача (тз)
- •1. Постановка тз
- •2. Математическая модель тз
- •3. Решение тз методом потенциалов
- •4. Проверка плана на оптимальность
- •5. Цикл пересчета
- •6. Метод дифференциальных рент
- •7. Дополнительные ограничения тз
- •Тема 9. Дискретное программирование
- •1. Задача целочисленного линейного программирования
- •2. Метод Гомори
- •3. Метод ветвей и границ
- •Тема 10. Элементы нелинейного программирования
- •1. Постановка задачи нелинейного программирования
- •2. Метод множителей Лагранжа
- •3. Задача выпуклого программирования
- •4. Задача квадратического программирования
- •Тема 11. Метод динамического программирования
- •1. Общая постановка задачи динамического программирования
- •2. Принцип оптимальности. Функциональные уравнения Беллмана
- •3. Задача оптимального распределения инвестиций
- •4. Задача о замене оборудования
- •Тема 12. Программирование на сетях
- •1. Основные понятия теории графов
- •2. Экстремальное дерево графа
- •3. Матричные способы задания графов. Упорядочение элементов орграфа
- •4. Потоки на сетях. Постановка задачи о максимальном потоке
- •5. Разрез на сети. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке
- •Тема 13. Планирование на сетях
- •1. Понятие сетевого графика
- •2. Основные параметры сг
- •3. Связь временных параметров сг
- •4. Алгоритм расчета параметров сг:
2. Правила построения двойственной злп
Существует много различных комбинаций ограничений и целевой функции для записи исходной задачи. Для упрощения задачи построения двойственной ЗЛП запишем прямую задачу в стандартном виде:
,
.
Правила построения двойственной ЗЛП:
1) Если прямая задача решается на максимум, то двойственная – на минимум, и наоборот.
2) В задаче на максимум ограничения-неравенства имеют смысл , а в задаче на минимум – .
3) Каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот.
4) Матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием.
5) Свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот.
6) Если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство.
7) Если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.
Пример. К данной ЗЛП составить двойственную задачу:
.
Преобразуем исходную ЗЛП к стандартному виду с максимизацией целевой функции:
.
Составим двойственную ЗЛП по ранее указанным правилам:
.
3. Основные теоремы двойственности и их экономическое содержание
Теоремы двойственности позволяют установить взаимосвязь между оптимальными решениями пары двойственных задач. Решив одну из пары двойственных задач, можно или найти оптимальное решение другой задачи, не решая ее, или установить его отсутствие. Возможны следующие случаи:
1) обе задачи из пары двойственных задач имеют оптимальные решения;
2) одна из задач не имеет решения ввиду неограниченности целевой функции, а другая – ввиду несовместности системы ограничений.
Теорема 5.1. (Основное неравенство теории двойственности) Для всех допустимых планов x и y пары взаимно двойственных задач справедливо неравенство F(x) ≤ Z(y).
Его экономическое содержание состоит в том, что для любого допустимого плана производства x и любого допустимого вектора оценок ресурсов y, общая созданная стоимость не превосходит суммарной оценки ресурсов.
Теорема 5.2. (Достаточный признак оптимальности) Если для некоторых допустимых планов x* и y* пары двойственных задач выполняется равенство F(x*)=Z(y*), то x* и y* являются оптимальными планами соответствующих задач.
Экономический смысл критерия: план производства x и вектор оценок ресурсов y являются оптимальными, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают.
Теорема 5.3. (Существование оптимальных планов пары двойственных задач) Для существования оптимального плана каждой из пары двойственных задач необходимо и достаточно существование допустимого плана для любой из них.
Теорема 5.4. Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций совпадают, то есть F(x*)=Z(y*). Если одна из двойственных задач неразрешима, вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.
Экономическое содержание теоремы: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов, причем цена продукта полученного в результате реализации оптимального плана совпадает с суммарной оценкой ресурсов.
Связь между задачами двойственной пары глубже, чем указано в формулировке теоремы: решая симплекс-методом одну из них, автоматически получаем решение другой. Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач и оценок в последней симплекс-таблице:
.
Теорема 5.5. Двойственная задача к двойственной есть прямая задача.
Теорема 5.6. Если пара двойственных задач имеет оптимальное решение, то при этом оптимальное значение переменных прямой задачи равно симплекс-множителям оптимального решения двойственной задачи, а значение переменных оптимального решения двойственной задачи равно симплекс-множителям оптимального решения прямой задачи.
Педагогический комментарий. Данное лекционное занятие закладывает основы для формирования следующих профессиональных умений студентов-экономистов: умение выявлять проблемы экономического характера при анализе конкретных ситуаций, предлагать способы их решения и оценивать ожидаемые результаты; умение разрабатывать и обосновывать варианты эффективных производственно-технологических решений; умение ставить цель и формулировать задачи, связанные с профессиональной деятельностью, умение использовать для их решения методы изученных дисциплин; умение логически мыслить; умение совершенствовать составление оперативно-производственного плана с использованием инструментария математического программирования; умение эффективно управлять экономическими процессами и регулировать использование комплекса имеющихся ресурсов; умение определять меру дефицитности ресурсов и оценку рентабельности или убыточности производимой продукции.