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

/

20

Федеральное агентство по образованию

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

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

Финансовый факультет

Кафедра компьютерных информационных систем финансовых расчетов

КОНТРОЛЬНАЯ РАБОТА

по дисциплине: «МАТЕМАТИКА»

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

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

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

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

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) .

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

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

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

,

.

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