Применение двойственных задач



Связь между решениями прямой и двойственной задачи на примере пары симметричных задач

Рассмотрим пару двойственных задач, образованную основной задачей линейного программирования и двойственной к ней.

Исходная задача: найти максимум функции

                                                                                                            (2.73)

при условиях

                                                                                (2.74)

.                                                                                              (2.75)

Двойственная задача: найти минимум функции

                                                                                                            (2.76)

при условиях

                                                                                 (2.77)

Каждая из задач двойственной пары (2.73).(2.75) и (2.76),(2.77) фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. при определении симплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи.

Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными леммами и теоремами двойственности.

Экономическая интерпретация двойственных задач (на примере). Экономический смысл 1-ой теоремы двойственности

План производства Xn*(x1*,x2*……xn*) и набор ресурсов (скрытых цен) Y*(y1*,y2*…..yn*) оказывается оптимальными тогда и только тогда, когда прибыль от продукции найденные при внешних (известных заранее) ценах С1,С»……Cn равна затратам на ресурсы при внутренних (опред-х только из условия задачи) цена Y1,Y2…..Yn

Для всех других планов X и Y обеих задач прибыль от продукции всегда меньше(или равна) затрат на ресурсы.

 

Оптимальные двойственные оценки и их смысл в задаче об использовании ресурсов.

 Если условная цена ресурса не равна 0, то это означает, что данный ресурс является дефицитным(кот. использ. полностью)

Значение оптимальной условной цены ресурсов показывает, на сколько увеличиться прибыль при увеличении запасов данного ресурса на 1.

 

Анализ моделей на устойчивость и чувствительность

на устойчивость - это исследование диапазона изменений правых частей систем при которых оптимальное решение остается неизменным.

на чувствительность – это исследование влияния небольших изменений условия задачи на оптимальное решение.

 

 

Метод искусственного базиса

ЗЛП, имеющие решения, не содержат единичной матрицы и не приводятся к указанному виду. В этом случае для решения задач применяется метод искусственного базиса.

решения задачи методом искусственного базиса:

1. Составляют расширенную задачу.

2. Находят опорный план расширенной задачи.

3. С помощью обычных вычислений симплекс-метода исключают искусственные векторы из базиса. В результате либо находят опорный план исходной задачи, либо устанавливают ее неразрешимость.

4. Используя найденный опорный план задачи, либо находят симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.

 

Т . Если в оптимальном плане =(x1, x2, ...,xn, 0, ..., 0) расширенной задачи искусственные переменные xn+i=0 (i=1,2,...,m), то план Х=(x1, x2, ..., xn) является оптимальным планом исходной задачи

Основные понятия теории игр

Одна из задач теории оптимальных решений — принятие решения в условиях неопределенности.

Теория игр представляет собой математическую теорию конфликтных ситуаций. Ее цель — выработка рекомендаций по разумному поведению участников конфликта.

Конфликтными называются ситуации, в которых сталкиваются интересы двух (или более) сторон, преследующих разные (иногда противоположные) цели, причем выигрыш каждой стороны зависит от того, как себя поведут другие. Примеры любая ситуация, складывающаяся в ходе боевых действий, ряд ситуаций в области экономики, судопроизводства, а также в спорте

Чтобы сделать возможным математический анализ конфликта, строится его математическая модель. Такую модель называют игрой.

От реального конфликта игра отличается тем, что ведется по определенным правилам. Эти правила указывают «права и обязанности» участников, а также исход игры — выигрыш или проигрыш каждого участника в зависимости от сложившейся обстановки. Отсюда и название теории игр, и ее терминология: конфликтующие стороны условно называются игроками, одно осуществление игры — партией, исход игры — выигрышем или проигрышем. Мы будем считать, что выигрыши (проигрыши) участников имеют количественное выражение

В игре могут сталкиваться интересы двух или более участников; в первом случае игра называется парной, во втором — множественной.

 Ходом называется выбор игроком одного из предусмотренных правилами игры действий и его осуществление. Ходы бывают личные и случайные. При личном ходе игрок – сам выбирает.При случайном- случай.

Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации.

Оптимальной стратегией игрока называется такая, которая обеспечивает ему наилучшее положение в данной игре, т. е. максимальный выигрыш. Если игра повторяется неоднократно и содержит, кроме личных, еще и случайные ходы, оптимальная стратегия обеспечивает максимальный средний выигрыш.

Задача теории игр — выявление оптимальных стратегий игроков. Основное предположение, исходя из которого находятся оптимальные стратегии, состоит в том, что противник (в общем случае — противники) по меньшей мере так же разумен, как и сам игрок, и делает все для того, чтобы добиться своей цели.


Дата добавления: 2018-05-12; просмотров: 935; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!