- •Математическая модель. Классификация и принципы построения математических моделей. Примеры задач, решаемых методами математического программирования.
- •Постановка и различные формы записи задач линейного программирования. Множество допустимых решений. Оптимальное решение задачи линейного программирования.
- •Стандартная и каноническая формы представления задач линейного программирования.
- •Геометрическая интерпретация задач линейного программирования. Многогранник решений. Алгоритм решения задачи линейного программирования графическим методом.
- •Геометрический смысл симплекс-метода решения задач линейного программирования. Построение начального опорного плана.
- •Симплекс-метод. Критерий оптимальности опорного плана.
- •Симплекс-метод. Правило перехода к новому опорному плану.
- •Симплекс-таблица. Пересчет симплекс-таблиц. Алгоритм симплекс-метода решения задач линейного программирования.
- •Метод искусственного базиса.
- •Экономическая интерпретация двойственных задач планирования производства.
- •Двойственная задача линейного программирования и алгоритм её формирования.
- •Формулировка теоремы двойственности. Нахождение оптимального плана двойственной задачи.
- •Анализ модели на устойчивость по отношению к изменениям запасов продукции (основная теорема).
- •Экономическая и математическая формулировки транспортной задачи.
- •Закрытая и открытая модели транспортной задачи. Приведение открытой транспортной задачи к закрытой.
- •Методы построения начального опорного плана транспортной задачи: метод северо-западного угла и метод минимального элемента.
- •Вырожденные и невырожденные планы транспортной задачи. Система потенциалов, экономический смысл. Критерий оптимальности опорного плана транспортной задачи.
- •Получение оптимального плана транспортной задачи с помощью метода потенциалов.
- •Алгоритм улучшения плана транспортной задачи. Понятие цикла, пересчет по циклу. Снятие вырожденности плана.
- •Транспортные задачи с ограничениями на пропускную способность сети.
- •Матричные игры. Платежная матрица. Игра с нулевой суммой.
- •Принцип минимакса и максимина. Верхняя и нижняя цена игры.
- •Оптимальные стратегии игроков. Решение матричной игры с седловой точкой.
- •Чистые и смешанные стратегии игроков. Вероятностная интерпретация. Теорема о существовании решения игры в смешанных стратегиях (теорема о минимаксе).
- •Графическое решение в случае игры 2 m и n2 .
- •Сведение решения игры в произвольном случае к задаче линейного программирования.
- •Математические модели межотраслевого баланса. Матрицы прямых и полных производственных затрат.
- •Валовой, конечный и чистый продукты. Определение цены конечной продукции.
- •Определение себестоимости продукции.
Геометрический смысл симплекс-метода решения задач линейного программирования. Построение начального опорного плана.
Симплекс-метод включает два этапа:
1) определение начального решения, удовлетворяющего ограничениям задачи;
2) последовательное улучшение начального решения и получение оптимального решения задачи.
Симплекс-метод. Критерий оптимальности опорного плана.
Для проверки решения на оптимальность просматривается последняя f- строка.
1) Если коэффициенты, стоящие при свободных переменных, неотрицательны, то полученное решение оптимально. Полученное решение единственно, если все эти коэффициенты положительны.
2) Если среди неотрицательных коэффициентов есть хотя бы один нулевой, то задача имеет бесконечное множество решений.
3) Если в последней строке есть хотя бы один отрицательный коэффициент, а в соответствующем этому коэффициенту столбце нет ни одного положительного элемента, то целевая функция f не ограничена на области допустимых решений.
4) Если хотя бы один из коэффициентов, стоящих при свободных переменных, отрицательный и в соответствующем ему столбце есть хотя бы один положительный элемент, то полученное решение может быть улучшено.
Симплекс-метод. Правило перехода к новому опорному плану.
Симплекс-таблица. Пересчет симплекс-таблиц. Алгоритм симплекс-метода решения задач линейного программирования.
Шаг 1. Получение начального решения.
Шаг 2. Выражение функции f только через свободные переменные.
Шаг 3. Проверка решения на оптимальность.
Шаг 4. Получение нового решения.
4.1. Выбор переменной, вводимой в список базисных переменных.
4.2. Выбор переменной, выводимой из списка базисных переменных.
4.3. Выполнение симплекс-преобразования и переход к новой симплекс-таблице.
Метод искусственного базиса.
Для многих задач линейного программирования, записанных в канонической форме и имеющих опорные планы, не всегда можно непосредственно указать m базисных переменных. В этом случае решение проводят в два этапа.
На I этапе вводятся искусственные переменные, необходимые для получения начального базиса. Записывается новая целевая функция, предусматривающая минимизацию суммы искусственных переменных при исходных ограничениях. Если минимальное значение новой целевой функции равно 0 (т.е. искусственные переменные исключены из базиса), то задача имеет допустимое решение: оптимальное решение, полученное на этапе I, используется в качестве начального решения исходной задачи (этап II). В противном случае (если не удалось вывести из базиса искусственные переменные), задача не имеет допустимого решения.
Экономическая интерпретация двойственных задач планирования производства.
Поясним экономический смысл двойственной модели.
Пусть в качестве управляющих переменных , , исходной модели рассматривается число изделий, производимых некоторым предприятием, а параметров - количество ресурсов, используемых для изготовления изделий. Через обозначено количество ресурсов i-того типа, идущее на изготовление одного изделия j- того вида, j - прибыль от реализации одного изделия j- того вида. Тогда исходная модель соответствует задаче определения оптимального плана производства продукции, обеспечивающего максимальную прибыль.
Пусть предприятие решило прекратить производство изделий и продать ресурсы, идущие на их изготовление. Обозначим через цену на единицу ресурсов j-того вида,
j =1,…,m. Цены на ресурсы должны удовлетворять следующим двум условиям: во-первых, они не должны быть слишком высокими, иначе ресурсы невозможно будет продать; а во-вторых, цены на ресурсы должны быть такими, чтобы прибыль от их реализации была больше прибыли от реализации готовой продукции. Первое условие выражается формулой , второе условие – ограничениями
В левой части каждого из неравенств стоит прибыль от продажи ресурсов всех типов, идущих на изготовление j- того изделия, в правой части – прибыль от продажи j- того изделия ( ).
Таким образом, двойственная задача соответствует следующей экономической проблеме: по каким минимальным ценам следует продавать ресурсы, чтобы прибыль от их реализации была больше прибыли, полученной от реализации продукции, изготавливаемой с помощью этих ресурсов.
Значения переменных часто называют теневыми ценами.