Выдержка из текста работы
Предприятие выпускает два вида продукции, используя три вида ресурсов. Известны: А — матрица норм затрат ресурсов, В — запасы ресурсов, С — прибыль на единицу продукции. С помощью данных, приведенных в таблице, требуется:
а) составить экономико-математическую модель и решить задачу планирования выпуска продукции, обеспечивающего получение максимальной прибыли;
б) составить действенную задачу, найти оптимальное решение и оптимум двойственной задачи с помощью теорем двойственности; указать дефицитные для предприятия ресурсы.
; ; .
а) ЭММ:
Х — ?;
целевая функция:;
система ограничений
естественное ограничение: .
Решение
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) .
Оптимальное решение задачи получается, используя решение предыдущей задачи линейного программирования и теоремы двойственности:
, минимальное значение целевой функции .
Определение оптимальной стратегии игрока А (учитывая ранее исключенные стратегии):
Ответ. Инвестор, вложив свои инвестиции в продукцию третьего вида на первом предприятии, выигрывает в полном объеме, извлекая максимальный и единственно возможный доход; выбрав же остальные стратегии, проигрывает полностью.
Размещено на
