- •1. Общая постановка задачи линейного программирования (лп)
- •2. Геометрический метод решения задач линейного
- •3. Симплексный метод решения задачи линейного
- •Двойственные задачи линейного программирования и их использование.
- •Анализ устойчивости двойственных оценок
- •7. Решение задачи линейного программирования с помощью excel
- •Microsoft Excel 8.0 Отчет по результатам
- •Microsoft Excel 8.0 Отчет по устойчивости
- •Microsoft Excel 8.0 Отчет по пределам
- •9. Задачи для контрольных заданий
- •Рекомендуемая литература Основной список
- •Дополнительный список
- •В ведение
- •1.Транспортная задача (тз)
- •1.1 Метод потенциалов.
- •1.2 Упрощенное представление решения.
- •1.3 Метод ранговых оценок
- •1.4. Определения оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке.
- •2. Примеры экономических задач которые могут быть решены с помощью транспортной модели.
- •2.1.Оптимальное распределение оборудования
- •2.2.Формирование оптимального штата фирмы.
- •2.3. Задача о назначениях.
- •2.4 Задача календарного планирования производства.
- •Модели без дефицита.
- •Модель с дефицитом.
- •Решение транспортной задачи на пк с помощью Excel.
- •4.Тестовые вопросы.
- •0613234 Дать общую формулировку транспортной задачи.
- •0622354 Коэффициенты Cij в функции цели транспортной задачи (Xij – количество перевозимого груза от I-го поставщика к j-ому потребителю) представляют собой:
- •0632234 Модель транспортной задачи называется закрытой, если:
- •0643242 Модель транспортной задачи называется открытой, если:
- •0653542 Перечислить методы построения исходного опорного плана
- •0662231 Построение опорного плана по методу минимальной стоимости в транспортной задаче начинается с клетки:
- •0673142 Построение первого опорного плана с помощью диагонального метода в транспортной задаче начинается с клетки:
- •0682453 Построение первого опорного плана с помощью о метода двойного предпочтения:
- •0692135 Опорный план транспортной задачи будет невырожденным, если он содержат в матрице перевозок следующее количество заполненных клеток
- •0763435 Косвенными тарифами в методе потенциалов транспортной задачи понимают сумму потенциалов поставщиков и потребителей:
- •0772345 Косвенный тариф в методе потенциалов транспортной задачи должен быть:
- •0781324 Что бы построенный план перевозок транспортной задачи (при использовании метода потенциалов) был оптимальным, сумма потенциалов поставщиков и потребителей для занятых клеток:
- •0792324 Циклом пересчета плана перевозок в транспортной задаче называется замкнутый многоугольник:
- •0803452 Новый план перевозок, полученный по циклу пересчета в транспортной задаче отличается тем, что:
- •0812415 Пересчет по циклу в транспортной задаче осуществляется для:
- •0821435 Оптимальный план транспортной задачи является единственным, если:
- •0832543 Замкнутый многоугольник, одна из вершин которого совпадает со свободной клеткой, а все остальные – с заполненными клетками называется:
- •0841432 Любой цикл пересчета в транспортной задаче имеет:
- •0852435 Какой из ответов не соответствует правилу пересчета по циклу?
- •0863441 Какой из ответов не удовлетворяет условию для последовательности неизвестных, находящихся в вершине цикла пересчета транспортной задачи?
- •0872234 В каком из приведенных примеров допущена ошибка возможного цикла пересчета в транспортной задаче?
- •0882143 Метод ранговых оценок используется если:
- •0891234 В методе ранговых оценок потенциалы – это оценки:
- •0913214 Решение транспортной задачи методом ранговых оценок заканчивается, когда:
- •5. Задачи контрольных заданий. Задание а
- •Задание 2
- •2. Задача № 31-60
- •Вопросы выносимые на зачет.
- •Предмет и задачи теории игр.
- •2 Матричные игры
- •3 Решение матричных игр в чистых стратегиях
- •4 Решение матричных игр в смешанных стратегиях
- •5 Непосредственное решение матричных игр
- •6 Пример решения матричной игры в смешанных стратегиях методом линейного программирования
- •7 Пример решение матричной игры в смешанных стратегиях с помощью персонального компьютера (пк)
- •8 Решение статистических игр по различным критериям
- •1. Критерий Вальда
- •3 Критерий Сэвиджа
- •9 Тестовые вопросы
- •0011234 Суть игры состоит в том, что:
- •0022134 Исход игры – это:
- •0034123 Стратегия игры – это:
- •10 Задачи контрольных заданий
- •2 Вопросы для промежуточной аттестации (экзамен)
- •11 Рекомендуемая литература
Двойственные задачи линейного программирования и их использование.
В математике встречаются ситуации, когда для некоторой задачи (назовем ее I) можно по определенным правилам построить другую задачу II, причем из решения задачи I автоматически вытекает решение задачи II и наоборот. Такие задачи I и II называют двойственными задачами.
Рассмотрим двойственные задачи линейного программирования на примере задачи о распределении ресурсов. Пусть предприятие выпускает несколько видов продукции: А1, А2, …, Аn, используя ресурсы: В1, В2, …, Вm, причем на изготовление единицы продукции Аj, (j = 1, …, n) требуется aij единиц ресурса Bi (i = 1, …, m). Производство обеспечено сырьем Bi в количестве bi (i = 1, …, m). Стоимость единицы продукции Аj составляет сj ден.ед. (j = 1, …, n). В качестве исходной задачи I возьмем задачу, изложенную в начале раздела 1.2.
Задача I. Пусть xj - неизвестное количество продукции Аj (j = 1, …, n). Требуется составить план производства, обеспечивающий наибольшую возможную выручку от продажи выпускаемой продукции. Задача формулируется в стандартной форме
a11x1+a12x2+…+a1nxn b1
a21x1+a22x2+…+a2nxn b2 (1.26)
…
Am1x1+am2x2+…+amnxn bm
f = c1x1 + c2x2 +… + cnxn Ì max
xj ≥ 0, j = 1, …, n.
Задача II, двойственнaя к исходной задаче I, состоит в следующем. Каковы должны быть цены (оценки) y1, y2, …, ym единицы ресурсов каждого типа, чтобы при заданных количествах ресурсов b1, b2, …, bm стоимости единицы изделий каждого вида c1, c2, …, cn общие затраты Z производства были минимальными.
Сформулируем эту задачу математически. Поскольку стоимость всех ресурсов, затраченных на изготовление единицы изделия каждого вида не может быть меньше стоимости этого изделия, то имеет место следующая система из n неравенств с m неизвестными:
a11y1+a21y2+…+am1ym c1
a12y1+a22y2+…+am2ym c2 (1.27)
………
a1ny1+a2ny2+…+amnym cn
а общие затраты производства (общая стоимость ресурсов) определяются целевой функцией Z = b1y1 + b2y2 + … + bmym, (1.28)
где yj ≥ 0 при всех j = 1,2, …, m (1.29)
Требуется найти такие значения переменных y1, y2, …, ym, которые удовлетворяли бы системе ограничений (1.27) и обеспечивали минимум целевой функции Z. Эту задачу в принципе также можно решить симплекс-методом.
Сопоставляя математические формулировки задач I и II, можно обнаружить следующие особенности:
Если в задаче I имеем m неравенств с n неизвестными (система 1.26), то в задаче II имеем m неравенств с n неизвестными (система 1.27); причем знаки неравенств изменяются на противоположные;
Если задача I – задача на максимум целевой функции, то задача II – на минимум другой целевой функции Z;
Коэффициенты aij в задаче I описываются матрицей норм затрат ресурсов, а коэффициенты aij в задаче II описываются транспонированной матрицей, полученной при перестановке местами строк и столбцов матрицы норм затрат ресурсов.
Рассматриваемую пару задач I и II называют симметричными двойственными задачами, так как система ограничений в них задана неравенствами вида «≤» и «≥» и на переменные xi и yj накладывается условие неотрицательности (xi ≥ 0, i = 1, 2, …, n; yj ≥ 0, j = 1, 2, …, m).
В теории линейного программирования доказана теорема двойственности, состоящая в том, что если одна из двойственных задач (I или II) имеет оптимальное решение, то и другая задача также имеет оптимальное решение, причем максимум целевой функции fmax прямой задачи и минимум целевой функции Zmin двойственной задачи численно равны, т.е. fmax = Zmin
Эта теорема широко используется при решении задач линейного программирования.
При решении двойственной задачи II для каждого ресурса находят определенное значение условной (теневой) цены единицы этого ресурса: y1, y2, …, ym, называемое двойственной оценкой ресурса. Двойственные оценки имеют конкретный экономический смысл и используются при анализе полученных в прямой задаче I оптимальных планов. С их помощью можно:
Выявить степень дефицитности каждого ресурса;
Определить приращение D f целевой функции f при увеличении запаса данного ресурса bj на одну единицу. При этом используются следующие свойства двойственных оценок y1, y2, …, ym.
А) Положительное значение y1 могут иметь лишь те виды ресурсов, которые полностью используются при оптимальном плане производства. Оценки ресурса, не полностью используемого в производстве, всегда равны нулю.
Б) Если мы желаем расширить производство, то анализ величин yj, j = 1, 2, …, m) позволяет выявить «узкие места», сдерживающие рост производства. Если yj > 0, то соответствующий вид ресурса является дефицитным. Чем больше величина yj , тем более дефицитным будет соответствующий вид ресурса. Если yj = 0, то соответствующий вид ресурса, вообще говоря, является избыточным. Т.е. на производстве имеется остаток этого ресурса.
В) Величина yj , j = 1, 2, …, m для каждого вида ресурса показывает, насколько возросло бы максимальное значение целевой функции f, если бы объем данного ресурса bj, j = 1, 2, …, m на производстве увеличился бы на единицу. Поэтому величины yj называют также теневыми ценами ресурсов bj, j = 1, 2, …, m.
Каждая из задач, прямая и двойственная к ней, являются самостоятельными задачами и могут решаться независимо друг от друга. Достоинством симплексного метода является то, что решение прямой задачи I автоматически приводит к решению и двойственной задачи II.
Решение задачи II, т.е. значения двойственных оценок y1, y2, …, ym можно найти непосредственно из последней строки симплекс-таблицы, оптимальной для прямой задачи I. Искомые значения y1, y2, …, ym равны элементам, лежащим на пересечении последней строки и столбцов, соответствующих дополнительным переменным.
В качестве примера определим двойственные оценки y1, y2, y3 для ресурсов трех видов и проведем анализ оптимального плана выпуска изделий А и Б для задачи I об использовании сырья, решенной симплексным методом в параграфе 3.
Двойственная задача формулируется следующим образом.
Условия производства описываются системой из n = 2 неравенств с m = 3 неизвестными y1, y2, y3. Система ограничений имеет вид:
(1.30)
Общая стоимость сырья определяется целевой функцией
Z = 400 y1+ 900 y2+ 600 y3 (1.31)
Требуется найти y1, y2, y3, удовлетворяющие системе неравенств (1.30) и обеспечивающие минимум функции (1.31).
При решении прямой задачи I получена оптимальная симплексная таблица 7. В нижней строке этой таблицы для дополнительных переменных x3, x4, x5 находим значения оценок y1= 24, y2 = 4, y3 = 0. Чтобы убедиться в правильности их вычисления, подставим полученные значения y1(j = 1, 2, 3) в выражение (1.31) для целевой функции Z
Zmin = 400*24 + 900*4 + 600*0 = 13200 (д. ед.) = fmax
Решение двойственных задач представляет интерес при планировании работы предприятий. Так как план производства и оценки ресурсов являются оптимальными тогда и только тогда, когда оценка производственной продукции и суммарная оценка ресурсов совпадают, то двойственные оценки можно использовать как инструмент балансирования затрат и результатов.
Решение двойственной задачи можно истолковать так: сырье 1-го и 2-го видов использовано полностью и имеет положительные оценки (теневые цены) y1= 24, y2 = 4. Сырье третьего вида использовано не полностью и его оценка y3 = 0.
Таким образом, двойственные оценки определяют дефицитность используемого сырья. Величина двойственной оценки показывает, насколько возрастет максимальное значение целевой функции f прямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение сырья первого вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства, при котором общая прибыль от реализации f возрастет на 24 (д. ед.). при этом числа в столбце, соответствующем x3, в таблице 7 оптимального плана, показывают, что указанное увеличение f может быть достигнуто за счет увеличения выпуска изделий вида А на 4/5 ед. и сокращения выпуска изделий вида В на 3/5 ед. Вследствие этого остатки используемого сырья 3-го вида возрастут на 1 кг. Точно так же увеличение на 1 кг сырья 2-го вида позволит найти такой план, при котором общая прибыль от выпуска изделий возрастет на 4 (д. ед.). Это будет достигнуто за счет увеличения выпуска изделий В на 4/5 ед. и уменьшения выпуска изделий А на 1/5 ед., причем остатки используемого сырья 3-го вида сократятся на 1 кг. При увеличении на 1 кг сырья 3-го вида значение функции f не изменится. Это означает, что сырье третьего вида – недефицитно. На практике сырье каждого вида целесообразно изменять таким образом, чтобы добавочная продукция составляла целое число единиц.
Двойственные оценки сырья можно использовать для определения меры влияния изменения запасов сырья на величину максимума выпуска продукции, чтобы выявить «узкие места» производства и наметить мероприятия по изменению ресурсов, обеспечивающих получение наибольшего экономического эффекта.
