- •Экономико-математические методы
- •1 Общая задача математического
- •1.1 Модель математического программирования
- •1.2 Математическая формулировка задач линейного
- •1.3 Примеры построения простейших моделей математического
- •1.4 Геометрическая интерпретация задач линейного
- •1.4.1 Графический метод решения
- •1.4.2 Схема решения задачи графическим методом
- •1.4.3 Особые случаи решения задач линейного
- •1.5 Контрольные вопросы к разделу 1
- •2 Симплекс-метод решения задач линейного
- •2.1 Симметричный симплекс-метод
- •2.2 Экономический анализ оптимального плана по последней
- •2.3 Симплекс-метод с искусственным базисом
- •2.4. Схема решения задач линейного программирования
- •2.5. Особые случаи при решении задач симплекс-методом
- •2.6 Контрольные вопросы к разделу 2
- •3 Двойственные задачи линейного
- •3.1 Понятие о двойственных задачах
- •3.2 Теоремы двойственности в линейном программировании
- •3.3 Экономическая интерпретация двойственных задач
- •3.4. Примеры построения двойственных задач
- •3.5 Контрольные вопросы к разделу 3
- •4 Транспортная задача линейного
- •4.1 Математическая постановка транспортной задачи
- •4.2 Метод потенциалов решения транспортной задачи
- •Числаui являются потенциалами строк, аvj – потенциалами столбцов. Из теоремы следует, что для того, чтобы план был оптимальным, необходимо выполнение следующих условий:
- •Если хотя бы одна незанятая клетка не удовлетворяет условию (б), то план не оптимален.
- •4.3 Схема решения транспортной задачи
- •4.4 Контрольные вопросы к разделу 4
- •5 Методы решения задач нелинейного
- •5.1 Классификация задач математического программирования
- •5.2 Метод Лагранжа
- •5.3 Метод динамического программирования
- •5.4 Применение динамического программирования для решения задач о замене оборудования и эффективного использования
- •5.5 Контрольные вопросы к разделу 5
- •6 Наиболее распространенные модели
- •Содержание
- •Литература
- •Экономико-математические методы Учебное пособие
4.3 Схема решения транспортной задачи
Перечислим основные этапы решения транспортной задачи.
1. Проверяют условие замкнутости. Если задача открытая, транспортную таблицу дополняют или столбцом фиктивного пункта потребления, или строкой фиктивного поставщика.
2. Строят опорный план.
3. Проверяют опорный план на невырожденность. Если для выполнения условия невырожденности не хватает занятой клетки, одну из клеток транспортной таблицы заполняют поставкой, равной нулю. При необходимости допустимо записывать нулевые поставки в несколько клеток.
4. План проверяют на оптимальность.
5. Если условия оптимальности не выполняются, переходят к следующему плану путем перераспределения поставок. Вычислительный процесс повторяется до получения оптимального плана.
4.4 Контрольные вопросы к разделу 4
1. Каков смысл целевой функции в математической модели транспортной задачи?
2.Каков смысл ограничений в математической модели транспортной задачи?
3. Можно ли применить метод потенциалов для решения открытой (незамкнутой) транспортной задачи?
4.Какие изменения необходимо внести в исходную транспортную таблицу, чтобы задачу можно было решить методом потенциалов?
5.В чем суть метода минимального элемента? Какой этап решения транспортной задачи будет выполнен в результате применения этого метода?
6. Как узнать является ли план перевозок оптимальным?
7. В каком случае и каким образом необходимо выполнить перераспределение поставок в плане перевозок?
8. Допустим построенный план перевозок является вырожденным. Можно ли продолжить решение задачи методом потенциалов и что для этого необходимо предпринять?
5 Методы решения задач нелинейного
ПРОГРАММИРОВАНИЯ
5.1 Классификация задач математического программирования
Общая задача математического программирования была сформулирована в разделе 1.1. В зависимости от типа функций, входящих в модель (1.1)-(1.3), задачу относят к тому или иному виду математического программирования. Различают линейное программирование (все функции линейны), целочисленное (решение представляют целые числа), квадратичное (целевая функция является квадратичной формой), нелинейное (хотя бы одна из функций задачи нелинейна) и стохастическое программирование (включены параметры, имеющие вероятностный характер).
Класс задач нелинейного программирования шире класса линейных моделей. Например, производственные затраты в большинстве случаев не пропорциональны объему выпуска, а зависят от него нелинейно, доход от реализации продуктов производства оказывается нелинейной функцией цен и т.д. Критериями в задачах оптимального планирования часто служат максимум прибыли, минимум себестоимости, минимум капитальных затрат. В качестве переменных величин выступают объемы выпуска различных видов продукции. В число ограничений входят производственные функции, характеризующие связь между выпуском продукции и затратами трудовых и материальных ресурсов, объем которых лимитирован.
В отличие от линейного программирования, в котором применяется универсальный метод решения (симплекс-метод), для решения нелинейных задач существует целый спектр методов в зависимости от формы входящих в модель функций. Из всего многообразия методов нами будут рассмотрены только два: метод Лагранжа и метод динамического программирования.