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

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

Рубрика Экономико-математическое моделирование
Вид контрольная работа
Язык русский
Дата добавления 02.01.2012
Размер файла 232,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

20

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

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

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

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

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

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

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

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

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

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

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

2010 г.

Вариант 5

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

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

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

; ; .

а) ЭММ:

Х - ?;

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

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

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

Решение

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

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

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

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

;

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

;

;

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

.

Рис. 1. График решения

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

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

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

,

, , , , , .

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

.

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

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

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

;\

Таблица 1

Номер симплекс-таблицы

Базис

10

20

0

0

0

0

0

40

4

2

1

0

0

20

0

90

6

9

0

1

0

10

0

20

1

2

0

0

1

10

0

-10

-20

0

0

0

1

0

20

2,667

0

1

-0,222

0

20

10

0,667

1

0

0,111

0

0

0

-0,333

0

0

-0,222

1

200

23,340

0

0

2,220

0

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

:

,

,

,

,

;

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

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

:

.

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

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

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

;

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

;

;

;

;

.

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

;

;

;

;

.

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

;

;

;

;

;

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

если и

если .

;

;

.

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

,

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

;

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

,

,

,

,

.

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

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

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

б) ЭММ:

Y - ?;

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

;

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

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

Решение

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

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

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

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

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

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

Таблица 2

Номер симплекс-таблицы

Ба-зис

10

20

0

0

0

0

0

40

4

2

1

0

0

20

0

90

6

9

0

1

0

10

0

20

1

2

0

0

1

10

0

-10

-20

0

0

0

1

0

20

2,667

0

1

-0,222

0

20

10

0,667

1

0

0,111

0

0

0

-0,333

0

0

-0,222

1

200

23,340

0

0

2,220

0

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

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

.

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

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

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

,

тогда

,

,

.

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

,

,

,

или

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

,

.

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

; если >0, то .

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

,

.

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

Анализ полученного оптимального решении исходной задачи с помощью двойственных оценок

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

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

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

, при .

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

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

.

Решение:

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

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

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

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

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

, где , ,

, где , .

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

1) ;

2) ;

3) ;

4) .

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

Таблица 3

Номер симплекс-таблицы

Базис

1

1

0

0

0

0

1

5

7

1

0

0,2

0

1

6

2

0

1

0,167

0

-1

-1

0

0

1

0

0,167

0

5,333

1

-0,833

1

0,167

1

0,333

0

0,167

0,167

0

1,333

0

0,167

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

;

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

:

,

,

,

;

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

.

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

:

.

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

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

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

;

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

;

;

;

.

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

;

;

;

.

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

если и

если .

;

.

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

,

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

;

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

,

,

,

.

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

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

,

.

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

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

1) ;

2) ;

3) ;

4) .

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

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

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

,

.

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

Размещено на Allbest.ru


Подобные документы

  • Задача оптимального планирования производства. Составление двойственной задачи, её решение по теоремам двойственности. Предельные вероятности состояний. Среднее время ожидания заявки в очереди. Принятие управленческих решений на основе теории игр.

    контрольная работа [218,5 K], добавлен 15.05.2015

  • Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.

    контрольная работа [467,8 K], добавлен 13.06.2012

  • Определение наиболее выгодного суточного объема выпуска изделий, обеспечивающего максимум прибыли. Построение математической модели задачи, ее решение графическим методом и в среде MS Excel. Расчет диапазона дефицитности ресурсов и дрейфа оптимума.

    контрольная работа [994,1 K], добавлен 16.02.2013

  • Пример решения типовой задачи оптимизации графическим методом. Получение оптимального плана выпуска продукции при помощи теории двойственности. Применение метода Леонтьева для построения баланса производства и распределения продукции предприятий.

    контрольная работа [2,2 M], добавлен 23.04.2013

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

    контрольная работа [161,9 K], добавлен 18.05.2015

  • Решение задачи линейного программирования графическим способом. Построение математической модели задачи с использованием симплекс-таблиц, её экономическая интерпретация. Поиск оптимального плана перевозки изделий, при котором расходы будут наименьшими.

    задача [579,8 K], добавлен 11.07.2010

  • Пример решения задачи симплексным методом, приведение ее к каноническому виду. Составление экономико-математической модели задачи. Расчеты оптимального объёма производства предприятия при достижении максимальной прибыли. Построение симплексной таблицы.

    практическая работа [58,0 K], добавлен 08.01.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.