- •§1. Постановка задачи.....................................................................46
- •§1. Основные понятия..................................................................61.
- •§1. Основные понятия.................................................................81
- •§1 Основные понятия.
- •§ 2 Классификация моделей
- •§ 3 Классификация решаемых экономических задач.
- •Классификация решаемых экономических задач.
- •Глава 2. Линейное программирование
- •§ 1 Общая постановка задачи
- •§ 2 Двойственность в задачах линейного программирования
- •Правила построения двойственной задачи по имеемой прямой задаче:
- •§ 3 Теоремы двойственности.
- •§4 Решение задач линейного программирования геометрическим методом
- •Алгоритм геометрического метода решения задач лп.
- •Рассмотрим задачу.
- •§ 5 Симплексный метод решения задач лп
- •Глава 3. Транспортная задача
- •§ 1 Постановка задачи.
- •§ 2 Алгоритм решения транспортных задач.
- •Метод наименьшего элемента.
- •Метод потенциалов.
- •§ 3 Примеры решения транспортных задач.
- •1.Проверяем задачу на сбалансированность.
- •Составляем математическую модель прямой и двойственной задач.
- •Решаем задачу по методу максимального элемента.
- •Глава 4 . Целочисленное программирование
- •§ 1 Постановка задачи целочисленного программирования.
- •§ 2 Графический метод решения задач целочисленного программирования.
- •Алгоритм графического решения задачи целочисленного программирования.
- •§ 3 Пример решения задачи целочисленного программирования.
- •Контрольные вопросы.
- •Глава 5 . Динамическое программирование
- •§1. Постановка задачи.
- •§2. Принцип оптимальности Беллмана.
- •§3. Задача распределения средств на 1 год
- •§4. Задача распределения средств на два года
- •Глава 6 . Управление производством.
- •§ 1 Управление производством.
- •§ 2 Управление запасами .Складская задача.
- •Глава 7. Теория игр.
- •§1 Основные понятия.
- •§2 Антагонистические игры.
- •Геометрический способ решения антагонистических игр
- •§3 Игры с « природой».
- •Пример №1
- •2. Критерий Гурвица.
- •3. Критерий Сэвиджа (критерий минимаксного риска).
- •4. Критерий Лапласа. N
- •Пример №2
- •Глава 8. Системы массового обслуживания
- •§I. Формулировка задачи и характеристики смо
- •§2 Смо с отказами
- •2.1 Основные понятия
- •2.2 Формулы для расчета установившегося режима
- •§3 Смо с неограниченным ожиданием
- •3.1 Основные понятия
- •3.2 Формулы для расчета установившегося режима
- •§4 Смо с ожиданием и с ограниченной длиной очереди
- •4.1 Основные понятия
- •4.2Формулы для установившегося режима
- •§5 Примеры решения задач.
- •Глава 9 нелинейное програмирование.
- •§1 Основные понятия.
- •§2 Математическая модель задачи.
- •§3 Безусловный экстремум
- •§4 Условный экстремум
- •Глава 10 . Сетевое планирование.
- •§1 Основные понятия метода сетевого планирования
- •Работа, события, путь.
- •Любая работа соединяет только 2 события.
- •§2 Расчет сетевых графиков
- •Содержание практических занятий
- •Рекомендуемая литература:
§ 2 Алгоритм решения транспортных задач.
-
Составить опорный план, т.е. начальное приближение.
-
Составить математическую модель исходной прямой и математическую модель двойственной задач.
-
Пользуясь методом наименьшего (наибольшего) элемента и методом потенциалов найти улучшение исходного опорного плана до тех пор, пока он не будет удовлетворять условию оптимальности.
-
Метод наименьшего элемента.
-
Сбалансировать задачу (убедиться, что задача сбалансирована).
-
Определить свободную клетку с наименьшей стоимостью перевозки. Если таких клеток несколько, то выбрать клетку с наибольшей потенциальной грузоперевозкой. Если и таких клеток несколько, то выбирается любая из этих клеток.
-
В выбранную клетку поставить максимально возможную грузоперевозку для потребителя от поставщика.
-
Проверить, остался ли нераспределенным груз у этого поставщика.
-
Если груз распределен не полностью, то применяем п.2 относительно строки этого поставщика. Продолжать до тех пор, пока груз этого поставщика будет полностью распределен.
Если груз поставщика распределен полностью, проверить, полностью ли удовлетворен объем потребителя.
Если потребитель полностью удовлетворен, то применить пункт 2 относительно оставшихся поставщиков и потребностей в таблице.
Если объем потребителя полностью не удовлетворен, тогда применяется пункт 2 относительно соответствующего столбца.
-
Проверить план на вырожденность. Количество базисных клеток должно быть равным r=m+n-1.
Если план вырожденный, то поставить фиктивное значение груза так, чтобы иметь возможность найти потенциалы всех базисных клеток (ставить нулевую перевозку).
-
Проверить на оптимальность и по возможности дальше улучшить, перейдя к методу потенциалов.
-
Метод потенциалов.
-
Для всех базисных клеток создать систему уравнений вида .
Выбрать переменную Ui или Vj, которой соответствует наибольшее количество занятых клеток, приравнять её к нулю, решить систему уравнений относительно Ui и Vj и найти эти значения.
-
Для всех свободных клеток составить и проверить выполнение неравенств:
Условия оптимальности: если для всех свободных клеток выполняется это неравенство, то тогда найден оптимальный план.
Если хотя бы для одной клетки не выполняется это неравенство, то необходимо улучшить опорный план с помощью коэффициента перераспределения W.
-
Находим клетку, где сильнее всего не выполняется неравенство. Если таких клеток несколько, то выбирается любая. В эту клетку ставим W со знаком «+».
-
Построить контур перераспределения груза, начиная с выбранной клетки, исходя из следующих правил:
-
В строке и столбце должно быть четное число W;
-
Контур меняет направление только в базисных клетках;
-
Коэффициент W меняет свой знак с «+» на «-» поочередно в углах контура.
-
После построения контура отметить, в каких базисных клетках коэффициент W стоит с отрицательным знаком. Из этих клеток найти клетку с наименьшим значением перевозки, коэффициент W будет равен перевозке в выбранной клетке.
-
Найти новый план, перераспределив найденное значение W по контуру с учетом знаков «+» и «-», прибавляя или уменьшая стоящую в клетке перевозку.
-
Проверить новый план в соответствии в п.2. если неравенства для свободных клеток выполняются, значит найденный план оптимален.
Если в математической модели целевая функция на максимум (Zmax), то задача решается методом максимального элемента, т.е. грузоперевозка (Xij) распределяется при составлении опорного плана с учетом наибольшего значения Cij аналогично метода наименьшего элемента. В методе потенциалов проверяется выполнение неравенства