- •1. Теория графов
- •1.1 Остовные деревья минимального веса.
- •Алгоритм Прим
- •Алгоритм Краскал
- •1.2 Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дийкстры
- •Алгоритм Дийкстры
- •Модифицированный алгоритм Дийкстры
- •1.3 Нахождение кратчайших цепей между всеми парами узлов в сети
- •Алгоритм Флойда (Floyd r. W.)
- •Модификация алгоритма Флойда
- •1.4 Построение потоков максимальной мощности. Алгоритм Форда-Фалкерсона
- •Алгоритм Форда-Фалкерсона
- •1.5 Обобщенные задачи о потоке
- •1.5.1 Построение потока в сети с двойным ограничением потока по дугам
- •1.5.2 Построение потока в сети с пропускными способностями узлов
- •1.5.3 Построение потока в сети с несколькими источниками-стоками
- •1.5.4 Построение потока в сети с неориентированными ребрами
- •1.6 Определение потока заданной величины минимальной стоимости. Алгоритмы Басакера-Гоуэна, Клейна
- •Алгоритм Басакера-Гоуэна (Basaker r.G., Gowen p.J)
- •Алгоритм Клейна (Klein m.)
- •2 Сетевое планирование
- •2.1 Построение сетевых моделей
- •2.2 Расчет и анализ сетевых моделей
- •Задача №1
- •Задача №2
- •I. Поиск критических путей
- •II. Поиск резервов работ
- •Правило №2.1
- •3 Линейное программирование
- •3.1 Примеры задач лп
- •3.2 Свойства решений задач линейного программирования
- •3.3 Двумерные задачи линейного программирования. Графический метод решения. Исследование на разрешимость
- •3.3.1 Построение области допустимых решений целевой функции f.
- •3.3.2 Построение прямой уровня
- •3.3.3 Максимизация целевой функции f
- •3.4 Симплекс-метод.
- •3.4.1 Построение начального опорного плана.
- •3.4.2 Симплексные таблицы
- •3.4.3 Примеры решения задач симплекс-методом
- •4. Теория двойственности в линейном программировании
- •4.1 Понятие двойственности. Построение пары взаимно двойственных задач
- •4.2 Теоремы двойственности и их экономическое содержание
- •4.3 Анализ решения задач линейного программирования
- •5. Транспортная задача
- •5.1 Постановка транспортной задачи в матричной форме. Построение исходного опорного плана
- •5.2 Метод потенциалов
- •5.3 Дополнительные условия в транспортных задачах.
- •6. Дискретное программирование.
- •6.1 Метод Гомори для решения задачи целочисленного линейного программирования
- •7. Динамическое программирование
- •7.1 Многошаговые процессы в динамических задачах
- •7.2 Принцип оптимальности и рекуррентные соотношения
- •7.3 Вычислительная схема динамического программирования
- •7.4 Оптимальное распределение средств на расширение производства
- •8. Матричные игры
- •8.1 Парные матричные игры с нулевой суммой
- •8.2 Платежная матрица
- •Нижняя и верхняя цена игры
- •8.3 Смешанные стратегии
- •8.3 Решение матричной игры сведением к задаче линейного программирования
- •8.4 Решение матричной игры графическим методом
- •8.5 Приближенный метод решения матричных игр
- •Практические работы Практическая работа №1 Построение остовного дерева графа. Нахождение найкратчайшего расстояния между заданными вершинами графа
- •Практическая работа №2 Нахождение наикратчайших расстояний между всеми парами вершин графа. Алгоритм Флойда.
- •Практическая работа №3
- •Практическая работа №4 Нахождение потока заданной величины минимальной стоимости. Алгоритм Басакера-Гоуэна
- •Практическая работа №7 Оптимизация проекта по времени.
- •Практическая работа №8
- •Практическая работа №9 Оптимизация целевой функции с помощью двухфазного симплекс метода.
- •Практическая работа №10 Решение двойственных задач. Экономическая интерпретация задач линейного программирования.
- •Практическая работа №11 Решение транспортных задач.
- •Практическая работа №12 Дополнительные условия в транспортных задачах
- •Практическая работа №13 Метод Гомори для решения задачи целочисленного линейного программирования.
- •Практическая работа №14
- •Практическая работа №15 Решение матричных игр в чистых стратегиях
- •Практическая работа №16 Графический метод решения матричных игр.
- •Каркас минимального веса. Метод р. Прима.
- •Кратчайшие пути
- •Лабораторная работа №2 Кратчайшее расстояния от заданной вершины до всех остальных вершин графа.
- •Алгоритм Дийкстры.
- •Пути в бесконтурном графе.
- •Лабораторная работа №3 Кратчайшие пути между всеми парами вершин графа.
- •Алгоритм Флойда.
- •Лабораторная работа №4 Построение потока максимальной мощности.
- •Потоки в сетях.
- •Метод построения максимального потока в сети.
- •Лабораторная работа №5 Симплекс метод
- •Лабораторная работа №6 Транспортная задача
- •Список литературы
4.3 Анализ решения задач линейного программирования
В математическом программировании доказывается следующая теорема двойственности (теорема об оценках).
Теорема 1. В оптимальном решении двойственной задачи значения переменных yi*(оценок) численно равны частным производным fmax / bi для исходной задачи.
Отсюда при малых изменениях bi свободных членов bi следует приближенное равенство
Некоторые аспекты применения двойственных оценок оптимального плана для его экономико-математического анализа рассмотрим на примере задачи рационального использования ресурсов по критерию максимума прибыли.
В матрично-векторной форме задача записывается следующим образом:
где - вектор прибыли продукции; - искомый вектор – план производства продукции; А- матрица коэффициентов при неизвестных – нормы потребления ресурсов; - вектор ограничений по ресурсам; - вектор оценок ресурсов.
Анализ задач линейного программирования может проводиться путем сопоставления различных вариантов решений; с помощью анализа внутренней структуры каждого из полученных решений, базирующегося на свойствах двойственных оценок, приведенных ниже.
Двойственные оценки являются:
показателем дефицитности ресурсов и продукции. Это их свойство следует из теоремы. Величина yi* является оценкой i-го ресурса. Чем больше значение оценки yi*, тем выше дефицитность ресурса. Для недефицитного ресурса yi* = 0;
показателем влияния ограничений на значение целевой функции. Ранее было отмечено, что yi* = fmax / bi. При незначительном приращении bi является точной мерой влияния ограничений на целевую функцию. Поэтому представляет интерес определение предельных значений ограничений (нижней и верхней границ), в которых величины оценок остаются неизменными;
показателем эффективности производства отдельных видов продукции с позиции критерия оптимальности. Это свойство следует из теоремы. Его суть заключается в том, что в оптимальный план может быть включена лишь та продукция j-го вида, для которой выполняется условие
инструментом сопоставления суммарных условных затрат и результатов. Это свойство следует из принципа двойственности, в котором устанавливается связь между значениями функций прямой и двойственной задач.
Из ранее данной экономической интерпретации двойственных задач следует, что равенство значений целевых функций при оптимальных планах означает, что оценка всех затрат производства должна равняться оценке производственного продукта.
Для целей анализа большое значение имеет матрица А-1 = dij, обратная матрице базиса оптимального плана A = аij.
Двойственные оценки можно использовать для экономического анализа решения при условии, что ограничения на ресурсы изменяются лишь в определенных пределах. В этой связи говорят о допустимом интервале устойчивости оценок. Интервал устойчивости оценок по отношению к i-му ограничению имеет вид
где называют нижним пределом уменьшения, а - верхним пределом увеличения и вычисляют по формулам:
Целесообразность включения в план новых видов продукции оценивается характеристикой
Если < 0, то данный вид продукции после введения в план улучшает его. При > 0 включение продукции в план нецелесообразно.
Пусть имеется возможность приобрести дополнительно i-й ресурс в объеме . Эта величина находится в пределах устойчивости двойственных оценок. Цена единицы ресурса равна ci. Следовательно, приращение прибыли в то время как затраты на приобретение ресурса составляют Данное мероприятие будет эффективным, если обеспечит дополнительную прибыль, т. е. если > 0, где
Пример. Для изготовления четырех видов продукции (А, Б, В и Г) используются три вида ресурсов (I, II, III). Наличие ресурсов, нормы их расхода на единицу продукции и получаемая прибыль от единицы продукции заданы в табл. Необходимо: а) найти оптимальные решения прямой и двойственной задач; б) определить изменение максимальной прибыли при изменении ресурсов: I вида – на -10ед., II – на +60, III – на +30 ед.; оценить раздельное и суммарное влияние этих изменений на величину максимальной прибыли; в) оценить целесообразность введения в план пятого вида продукции Д, нормы затрат ресурсов на единицу которого равны соответственно 2, 4, 2, а прибыль – 15; г) оценить целесообразность закупки 100 ед. ресурса III вида по цене c3 = 0,5.
Таблица 4.5
Вид ресурса |
Запас ресурса |
Норма расхода на единицу продукции |
|||
А |
Б |
В |
Г |
||
I II III |
240 60 300 |
2 1 1 |
1 0 2 |
1 2 1 |
3 1 0 |
Прибыль |
4 |
2 |
3 |
5 |
Решение Математическая модель задачи имеет вид:
а)Решаем задачу симплекс-методом (опуская подробности, приведем сразу оптимальное решение в табл.4.6).
Таблица 4.6
Б
СП |
1 |
-x2 |
-x5 |
-x7 |
-x6 |
x1= x2= x3= |
60 120 0 |
11/5 -4/5 -3/5 |
4/5 -1/5 -2/5 |
-2/5 3/5 1/5 |
-1/5 -1/5 3/5 |
f = |
480 |
2/5 |
8/5 |
1/5 |
3/5 |
Значения целевой функции и неизвестных величин оптимального плана следующие: f* = 480, х1* = 60, х2* = 120, х3* = 0, х4* = х5* = х6* = х7* = 0.
Базисными неизвестными, входящими в оптимальный план, являются х1, х2 и х3. Выпишем матрицу из коэффициентов при базисных неизвестных:
Из табл. выпишем матрицу, обратную матрице А,
Используя соответствие между переменными исходной и двойственной задач, запишем оптимальное решение двойственной задачи: y1* = 8/5, y2* = 3/5, y3* = 1/5, y4* = y5* = y6* = 0, y7* = 2/5, f(y)min= 480. Как показывают значения оценок, наиболее дефицитным является ресурс I, так как y1* = 8/5, а наименее дефицитным – ресурс III, так как y3* = 1/5.
Чтобы определить изменение максимальной прибыли при изменении ресурсов, необходимо найти интервалы устойчивости двойственных оценок, в пределах которых они точно измеряют влияние ограничений на целевую функцию.
Определим интервал устойчивости оценок по отношению к ограничению по ресурсу I вида. Используя формулы находим:
В соответствии с формулами интервал устойчивости оценок по отношению к первому ограничению принимает следующий вид:
Аналогичным образом находим интервалы устойчивости оценок по отношению к ограничениям по двум другим видам ресурсов: по ресурсу II - 60;360, по ресурсу III - 300;450.
б) Так как изменения ресурсов находятся в пределах устойчивости оценок, то их раздельное влияние на величину прибыли определяется произведением оценки и величины изменения . Таким образом,
Суммарное влияние
в) Оценим целесообразность введения в план пятого вида продукции (Д). Для этого по формуле вычислим характеристику:
Так как прибыль превышает затраты, введение в план пятого вида продукции выгодно.
г) Приращение третьего ресурса на величину находится в пределах устойчивости двойственных оценок. Следовательно, в то время как затраты на приобретение 100 ед. ресурса III вида Поскольку величина p дополнительной прибыли отрицательна (p3 = f3 - c3 = 20 - 50 = -30), закупать ресурс III вида нецелесообразно.