Линейное программирование, теория игр

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования

«НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. И. ЛОБАЧЕВСКОГО»

Финансовый факультет Кафедра компьютерных информационных систем финансовых расчетов КОНТРОЛЬНАЯ РАБОТА по дисциплине: «МАТЕМАТИКА»

«Линейное программирование, теория игр»

Выполнил: Коршунов Р. М.

Проверила: Отделкина А. А.

Нижний Новгород

2010 г.

Вариант 5

Предприятие выпускает два вида продукции, используя три вида ресурсов. Известны: А — матрица норм затрат ресурсов, В — запасы ресурсов, С — прибыль на единицу продукции. С помощью данных, приведенных в таблице, требуется:

а) составить экономико-математическую модель и решить задачу планирования выпуска продукции, обеспечивающего получение максимальной прибыли;

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

;; .

а) ЭММ:

Х — ?;

целевая функция:;

система ограничений естественное ограничение: .

Решение

1. Графический метод:

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

· выбирается точка (1; 1), лежащая внутри многоугольника и определяется область решений, подставляя её координаты в функциональные неравенства. В результате чего ОДР является замкнутый многоугольник (на рис. 1 — заштрихованная область). Любая точка этого многоугольника удовлетворяет всем трем функциональным неравенствам, а для любой точки вне этого многоугольника хотя бы одно неравенство будет нарушено;

· для определения направления движения к оптимуму строится вектор-градиент, координаты которого являются частными производными целевой функции: модель двойственный задача

;

· строится линия уровня. Приравнивается целевая функция постоянной величине a. Меняя значение a, получается семейство параллельных прямых, каждая из которых является линией уровня целевой функции:

;

;

передвигая линию до ее выхода из ОДР, определяется максимум. В данном случае (при максимизации целевой функции) движение линии уровня осуществляется в направлении градиента. В крайней угловой точке достигается максимум целевой функции

.

Рис. 1. График решения Ответ. Для получения максимальной прибыли (200) необходимо выпустить 10 наименований второго вида продукции () и не выпускать продукцию первого вида.

2. Симплексный метод.

Приводится задача к каноническому виду путем введения дополнительных переменных, ,. В целевую функцию эти переменные включаются с нулевыми коэффициентами:

, ,, , .

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

.

Составляется симплексная таблица (табл. 1). В данном примере m=3, n=5.

Вычисляются значения (m+1)-й строки нулевой симплексной таблицы:

а) значение целевой функции

;

Таблица 1

б) значения симплекс-разностей

:

;

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

В базис включается вектор, а исключается из базиса тот вектор, которому соответствует

:

.

Минимальное положительное оценочное отношение Q, равное 10, соответствует вектору, который выводится из базиса.

В нулевой симплексной таблице разрешающим элементом является .

Значение целевой функции в следующей симплекс-таблице (s=1) будет равно:

;

г) находятся элементы i-й строки в новой симплекс-таблице по формуле:

;

;

;

;

.

Элементы направляющей r-й строки вычисляются по следующей формуле:

;

;

;

;

.

Оставшиеся элементы i-й строки в новой симплекс-таблице

;

;

;

;

;

д) определяются значения нового опорного плана по формулам:

если и

если .

;

;

.

В результате вычислений получен следующий опорный план:

значение целевой функции при этом

;

е) проверяется полученный план на оптимальность. Вычисляются симплекс-разности:

.

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

Ответ. Все симплекс-разности в первой симплексной таблице неотрицательны, следовательно, план является оптимальным.

Значение целевой функции .

б) ЭММ:

Y — ?;

целевая функция:

;

система ограничений естественное ограничение: .

Решение Решение двойственных задач основывается на теориях двойственности.

1. Решение двойственной задачи, основанное на первой теореме.

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

Следовательно, основные переменные:

Дополнительные переменные:

Составим симлекс-таблицу для двойственной задачи Таблица 2

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

Значение целевой функции:

.

Решение двойственной задачи, основанное на второй теореме.

Необходимо найти такие «цены» на ресурсы, чтобы общая стоимость используемых ресурсов была минимальной.

Воспользуемся следующим соотношением второй теоремы двойственности:

тогда

.

Необходимо подставить оптимальные значения вектора в полученные выражения:

или

так как 20<40, то ,

.

В следующем вычислении применяется вторая формула второй теоремы:

; если >0, то .

В данном примере, поэтому второе ограничение двойственной задачи обращается в равенство:

.

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

Анализ полученного оптимального решении исходной задачи с помощью двойственных оценок Ресурс имеет отличную от нуля оценку 2,220 — этот ресурс полностью используют в оптимальном плане и он является дефицитным, т. е. сдерживающим рост целевой функции.

Ресурс используется не полностью (20<40), поэтому имеет нулевую двойственную оценку (=0). Этот ресурс не влияет на план выпуска продукции.

Ответ. Оптимальный план двойственной задачи определен верно:

при .

Ресурс используется полностью и является дефицитным для предприятия.

Составить модель задачи — игры определения оптимальных пропорций инвестиций по предприятиям. Цель инвестора — получение максимального дохода. Известны доходы на вложенный рубль в продукцию i-того вида на j-том предприятии по каждому предприятию. Требуется: а) упростить платежную матрицу игры; б) свести задачу относительно инвестора к задаче линейного программирования и найти ее решение симплексным методом; в) найти оптимальные пропорции инвестиций по предприятиям и видам продукции.

.

Решение:

а) упрощение игры.

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

Платежная матрица упрощенной игры имеет вид:

б) необходимо определить нижнюю и верхнюю цену игры.

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

где, ,

где, .

Необходимо свести игру (относительно игрока В) к задаче линейного программирования.

1) ;

2) ;

3) ;

4) .

Составим симплекс-таблицу Таблица 3

а) значение целевой функции

;

б) значения симплекс-разностей

:

;

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

.

В базис включается вектор, а исключается из базиса тот вектор, которому соответствует

:

.

Минимальное положительное оценочное отношение Q, равное 0,167, соот-ветствует вектору, который выводится из базиса.

В нулевой симплексной таблице разрешающим элементом является .

Значение целевой функции в следующей симплекс-таблице (s=1) будет равно:

;

г) находятся элементы i-й строки в новой симплекс-таблице по формуле:

;

;

;

.

Элементы направляющей r-й строки вычисляются по следующей формуле:

;

;

;

.

д) определяются значения нового опорного плана по формулам:

если и

если .

;

.

В результате вычислений получен следующий опорный план:

значение целевой функции при этом

;

е) проверяется полученный план на оптимальность. Вычисляются симплекс-разности:

.

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

Определение оптимальной стратегии игрока В:

.

Смешанная стратегия игрока В представляет собой .

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

1) ;

2) ;

3) ;

4) .

Оптимальное решение задачи получается, используя решение предыдущей задачи линейного программирования и теоремы двойственности:

минимальное значение целевой функции .

Определение оптимальной стратегии игрока, А (учитывая ранее исключенные стратегии):

.

Ответ. Инвестор, вложив свои инвестиции в продукцию третьего вида на первом предприятии, выигрывает в полном объеме, извлекая максимальный и единственно возможный доход; выбрав же остальные стратегии, проигрывает полностью.