Решите графическим методом задачу линейного программирования.
f (X) = 2x1+x2
x1+x2 >=3
2x1+3x2<=15
2x1-2,5x2<=10
0<= x2<=4
x1>=0
Решение:
Данную задачу мы будем решать с помощью надстройки Поиск решения – это надстройка EXCEL, которая позволяет решать оптимизационные задачи.
На лист Ms EXCEL переносим параметры следующим образом

Здесь в первой строке стоят коэффициенты целевой функции, а в последующих коэффициенты ограничений, включая условия неотрицательности. Коэффициенты для х1 стоят в первой колонке, а коэффициенты для Х2 – во второй. В строках ограничений через пустую ячейку стоят значения правых частей ограничений.

Вводим зависимость для целевой функции, для этого используем функцию СУММПРОИЗВ. Для этого помещаем курсор в ячейку D3 и используем функцию СУММПРОИЗВ, в качестве МАССИВА1 вводим значения ячеек $B$2 и $C$2 (закрепляем значения ячеек, чтобы при копировании формулы в другие ячейки эти значения не изменялись), в качестве МАССИВА2 вводим
B3 и C3. Получаем значение ячейки D3, далее копируем формулу в ячейки D4:D9.

Далее вызываем Поиск решения ( в меню – Сервис Поиск решения)
В диалоговом окне Поиск решения есть три основных параметра:
Установить целевую ячейку
Изменяя ячейки
Ограничения
Сначала нужно заполнить поле «Установить целевую ячейку», для этого выделяем ячейку $D$3, вводим направление целевой функции: Максимальное значение/ Минимальное значение. В поле «Изменяя ячейки» вводим адреса $B$2:$C$2. Вводим ограничения, курсор в поле «Добавить», появится диалоговое окно Добавление ограничений. В поле «Ссылка на ячейку» ввести адрес $D$4.Ввести знак ограничения >=. Курсор в правое окно, ввести адрес $E$4, Добавить. На экране опять диалоговое окно Добавление ограничений, вводим остальные ограничения, после ввода последнего ограничения вводим ОК. На экране появится диалоговое окно Поиск решения с введенными условиями. Нажимаем кнопку Выполнить. При поиске минимального значения получаем следующие значения.

При поиске максимального значения получаем


2.Решите симплекс – методом задачи линейного программирования.

2.1. min f (X) =x1 – 4x2 2.2 max f (X)= (x1-24x2+12x3)
x1 + x2<= 5, -x1-3x2+2x3<=1,
3x1 – x2<=3, -x1+4x2-x3>=2,
x1.2>=0 x1,2,3>=0
2.1.Решение ЗЛП с естественным базисом.
В каноническом виде ЗЛП имеет вид:
найти max f(X) = - x1 + 4x2
при ограничениях x1 + x2<= 5,
3x1 – x2<=3,
x1.2>=0
Строим симплекс таблицу:

При заполнении столбца сi, берём значения из начальной строки таблицы сj, соответствующие базисным векторам .
При вычислении "дельта" в ячейке Е7 используем формулу “=$C$5*E5+$C$6*E6 - E3”, далее копируем формулу в ячейки F7:H7. По результатам вычисления можно увидеть, что направляющим столбцом будет столбец А2. Для того чтобы узнать какой будет направляющей строка находим значения Q, для этого поделим компонент вектора В на компоненты вектор А2. По результатам вычислений получается, что направляющей строкой является А3, а направляющий элемент 1.
При построении следующей таблицы используем разные формулы при перерасчете компонентов векторов В и Аi. Поскольку направляющей строкой в О-й таблице является первая строка, то при вычислении первой строки в 1-й таблице компоненты всех векторов делим на направляющий элемент.
При вычислении элементов второй строки используем соответствующую формулу, которая применяется для строк , не являющихся направляющими.
Например, для ячейки Е9 используем формулу ” =(E6*$F$5-E5*$F$6)/$F$5”, далее копируем формулу в остальные ячейки. После вычисляем “дельту”, по ранее названной формуле, все значения получаются положительными, значит задачу можно считать решенной. Получается, что А2 = 5, А4 = 8.

При решении этой же задачи с использованием Поиска решения получается аналогичное решение




2.2. Решение ЗЛП с искусственным базисом
найти max f (X)= (x1-24x2+12x3)
при ограничениях: -x1-3x2+2x3<=1,
-x1+4x2-x3>=2,
x1,2,3>=0
Здесь все аналогично вычислениям предыдущей задачи за исключением использования числа М. Мы выносим его в отдельную ячейку, будем ссылаться на нее в формулах. В качестве начального значения М возьмем 1000.
Вычисляем “дельту” для ячейки Е22 используя формулу
” =E20*$C$20+E21*$C$21-E18”, для остальных ячеек копируем формулу.
По результатам вычислений направляющим столбцом оказался А2, ищем направляющую строку, находя значение Q. По результатам вычислений получается, что направляющей строкой является А7, а направляющим элементом 4.
Для 1-ой и 2–ой таблицы используем те же формулы, что и для примера 2.1.
По результатам таблицы 2 , получается, что А1=0, А2=1, А3=2. Проверяем полученные значения с помощью функции Поиск решения

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

При решении задачи на максимум общей стоимости выпускаемой продукции (вся готовая продукция реализуется) были получены следующие результаты:
Х1=520, Х2=0, Х3=110.
Требуется:
Сформулировать прямую оптимизационную задачу на максимум общей стоимости выпускаемой продукции, пояснить нулевые значения Х2;
Сформулировать двойственную задачу и найти ее оптимальный план;
Проанализировать использование ресурсов в оптимальном плане;
Определить, как изменяется общая стоимость продукции и план ее выпуска при увеличении запаса сырья 1 на 24;
Определить целесообразность включения в план изделия четвертого вида ценой 11ед., если нормы затрат ресурсов 8,4, 20 и 6 ед.
Решение: 1) Обозначим Х1,Х2,Х3,Х4 – нормы расходов ресурсов на ед. продукции. Целевая функция будет выглядеть следующим образом: max f(X)=(6Х1+10Х2+9Х3), при ограничениях:
3Х1+6Х2+4Х3<=2000
20Х1+15Х2+20Х3 <=15000
10Х1+15Х2+20Х3<=7400
3Х2+5Х3<=1500
Х1,2,3>=0
Решением задачи является Х*= (520;0;110), а значение целевой функции будет равно 6*520+10*0+9*110 = 4110
2) Целевая функция двойственной задачи формулируется на минимум. Коэффициент при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи.
min g(Y)=2000Y1+15000Y2+7400Y3+1500Y4, при ограничениях
3Y1+20Y2+10Y3>=6
6Y1+15Y2+15Y3+3Y4>=10
4Y1+20Y2+20Y3+5Y4>=9
Y1,2,3,4>=0
Решение двойственной задачи можно найти в отчете
Количество неизвестных в двойственной задаче равно числу функциональных ограничений в исходной задаче. В исходной задаче четыре ограничения: по труду, по сырью1, сырью2, по оборудованию. Следовательно, в двойственной задаче четыре неизвестных:
Y1 – двойственная оценка ресурса «труд»
Y2 – двойственная оценка ресурса «сырье1»
Y3 – двойственная оценка ресурса «сырье2»
Y 4 – двойственная оценка ресурса «оборудование»
Целевая функция двойственной задачи формулируется на минимум. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений в исходной задаче.
g (yср) = 2000Y1+15000Y2+7400Y3+1500Y4 min
Необходимо найти такие «цены » на ресурсы, чтобы общая стоимость используемых ресурсов была минимальной.
Правыми частями в ограничениях двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной задачи. Левая часть ограничений определяет стоимость ресурсов, затраченных на производство единицы продукции. Каждое ограничение соответствует определенному виду продукции.
3Y1+20Y2+10Y3>=6
6Y1+15Y2+15Y3+3Y4>=10
4Y1+20Y2+20Y3+5Y4>=9
Y1,2,3,4>=0
Решение двойственной задачи можно найти в отчете Поиска решений – отчете по устойчивости. Теневые цены ресурсов труда, сырья1,сырья2,оборудования соответственно равны 1,5 ;0 ; 0;15,0.

3) Проведем анализ полученного оптимального решения исходной задачи с помощью двойственных оценок.
1. Анализ использования ресурсов в оптимальном плане выполняется с помощью соотношений 2-й теоремы двойственности:
если Yi>0, то EMBED Equation.3 *Xj= bj, i=1,…,m;
если EMBED Equation.3 *Xj< bj, то Yi = 0, i=1,..,m.
Ресурсы труд и сырье 2 имеют отличные от нуля оценки 1,5 и 0,15 – эти ресурсы полностью используются в оптимальном плане, являются дефицитными, сдерживающими рост целевой функции. Правые части этих ограничений равны левым частям:
3Х1+6Х2+4Х3<=2000
10Х1+15Х2+20Х3<=7400
3*520+6*0+4*110=2000=2000
10*520+15*0+20*110=7400=7400
Ресурс «сырье1» и «оборудование» используется не полностью, поэтому имеют двойственные нулевые оценки(Y1,Y2=0).
20Х1+15Х2+20Х3<=15000
3X2+5X3<=1500
20*520+15*0+20*110=12600<15000
3*0+5*110=550<1500
Эти ресурсы не влияют на план выпуска продукции. Нулевая оценка ресурсов свидетельствует о их недефицитности.
Общая стоимость ресурсов при выпуске 520 ресурсов 1 вида, 110 ресурсов 3 вида составила 4110.
g (уср)= 2000Х1+15000Х2+7400Х3+1500Х4 = 2000*1,5+15000*0+7400*0,15+1500*0=4100
4) Необходимо знать такие интервалы изменения каждого из свободных членов системы ограничений исходной ЗЛП, или интервалы устойчивости двойственных оценок, в которых оптимальный план двойственной задачи не менялся бы. В нашей задаче в нижеприведенном фрагменте видно, что запасы ресурса «сырье1» могут быть как уменьшены, так и увеличены.


Увеличения запаса ресурса «сырье1» до 15024 не повлияло ни на план выпуска продукции, ни на общую стоимость продукции. Изменился только предел допустимого уменьшения до 2424.
5) ?= 8Y1+4Y2+20Y3+6Y4 - 11 = 8*1.5+4*0+20*0,15+6*0-11=4>0 – целесообразно.

4.Заданы матрицы коэффициентов прямых затрат трех отраслей А=(aij) и вектор конечной продукции Y.
Требуется:
Проверить продуктивность матрицы А;
Построить баланс производства и распределения продукции отраслей.
1) проверка продуктивности матрицы А
Используя матричные функции EXCEL, легко проверить одно из двух следующих условий, необходимых для того чтобы матрица была продуктивна:
а) Матрица (Е –А) неотрицательно обратима, т.е. существует обратная матрица (Е – А)-1 и все ее элементы неотрицательны.
б) Положительны все главные миноры матрицы (Е – А).
а) сначала запишем единичную матрицу и вычтем из нее матрицу. А

Обратную находим с помощью функции МОБР, получаем следующие значения
Так как все элементы обратной матрицы положительны, значит выполняется условие а), а матрица продуктивна.
б) Нужно вычислить все главные миноры и проверить на неотрицательность.
Первый из них 0,9>0.
Второй минор находим с помощью функции МОПРЕД, где в качестве массива выделяем ячейки В19:С20, получаем значение 0,01>0.
Третий минор ищем таким же образом, получаем значение 0,001>0.
Все миноры положительны, значит выполняется условие б), матрица продуктивна.
2)Построение межотраслевого баланса.
Для вычисления вектора валовой продукции Х, нужно матрицу (Е – А)-1 умножить на вектор Y с помощью функции МУМНОЖ, где в качестве массива1 выделим ячейки B19:D21, а в качестве массива2 вектор Y.

Для получения распределительной части баланса нужно перемножить первый столбец матрицы А на первый элемент вектора Х, второй столбец – на второй элемент, третий - на третий.
Для проверки вычислений можно сложить элементы строки распределительного баланса друг с другом и с соответствующим элементом вектораY. В результате должен получиться вектор Х.
Все получилось, теперь можно собрать все составляющие баланса в одну таблицу.
5.
Требуется:
сгладить Y(t) с помощью простой скользящей средней;
определить наличие тренда Yp(t);
построить линейную модель Yp(t) = а0+а1xt , параметры которой оценить МНК;
построить адаптивную модель Брауна Yp(t) = а0+а1xk с параметром сглаживания а=0,4 и а=0,7; выбрать лучшее значение а;
оценить адекватность построенных моделей на основе исследования:
случайности остаточной компоненты по критерию пиков;
независимости уровней ряда остатков по d-критерию ( качестве критических используйте уровни d1= 1,08 и d2=1,36) или по первому коэффициенту корреляции, критический уровень которого, r(1)=0,36.
1);2) Строим вспомогательную таблицу со сглаженными значениями показателя
Y ( интервал сглаживания равен 3). Для заполнения основной части таблицы задаем формулу, например для ячейки Е2 это “=(В2+В3+В4)/3”. Для нахождения остальных ячеек копируем формулу. По получившейся таблице строим график зависимости сглаженного показателя от t, для этого используем “Мастер диаграмм”
EMBED Excel.Chart.8 \s
График сглаженной функции показывает, что имеется тенденция роста показателя с течением времени.
Построить вспомогательную таблицу для исследования линейной модели.

Далее строим график, на котором отражены результаты наблюдений и линейная модель.
EMBED Excel.Chart.8 \s
Первым этапом при построении модели Брауна является нахождение коэффициентов а0(0) и а1(0) по нескольким первым наблюдениям. Проведем вычисление коэффициентов по 3-м наблюдениям.

Таким образом мы получили нужные нам а0(0) и а1(0), теперь нужно построить вспомогательную таблицу для нахождения расчетных значений по модели Брауна. Предварительно нужно задать ? (в условии 0,6 – при ?=0,4 или 0,3 при ?=0,7). При ?=0,3, получаем следующие данные:
А при ?=0,6:
Сравнивая значения Еотн.ср – средней ошибки аппроксимации, можно сказать, что при ?=0,6 эта величина меньше, следовательно модель получилась более точной и наилучшей.
EMBED Excel.Chart.8 \s
5)
1. Проверку адекватности построенной модели проведем на основе исследования случайности остаточной компоненты по критерию пиков.

Используя формулы:
В нашем случае р =6, р = 4,667, ?2р =1,278, а неравенство выглядит следующим образом: 6>2 , т.е. неравенство выполняется. Следовательно, можно сделать вывод, что свойство случайности ряда остатков подтверждается.
2. Для оценки адекватности построенных моделей на основе исследования независимости уровней ряда остатков по d- критерию строим дополнительные столбы в нашей таблице:

Используя формулу 5.12, получаем d = 101,64/42,73 = 2,38. Эта величина превышает 2, что свидетельствует об отрицательности автокорреляции, поэтому критерий Дарбина –Уотсона необходимо преобразовать:d’ =4 – d = 4 – 2,38 = 1,62. Данное значение сравниваем с двумя критическими табличными значениями критерия, которые для линейной модели в нашем случае можно принять равными d1=1,08 и d2=1,36. Так как расчетное значение попадает в интервал от d2 до 2, то делается вывод о независимости уровней остаточной последовательности. Отсюда следует, что остаточная последовательность удовлетворяет всем свойствам случайной компоненты временного ряда, значит, построенная модель является адекватной. Для характеристики точности модели воспользуемся показателем средней относительной ошибки аппроксимации, который рассчитывается по формуле 5.14: Еотн.ср. = 32,43/9 = 3,60 (%). Полученное значение средней относительной ошибки говорит о достаточно высоком уровне точности построенной модели.
6.Оптовый склад обслуживает 30 предприятий-потребителей материалов. Каждое из предприятий направляет на склад автомашину в среднем один раз в смену (смена – 8 ч.). Средняя продолжительность погрузки одной машины составила 48 мин., т.е. 0,1 смены. Погрузка осуществляется кранами. Потери склада связанные с простоем крана (включая крановщика и стропальщиков) из-за отсутствия автомашин, равны 5 у.е./ч.
Прибывшая на склад автомашина становится в очередь, если все краны заняты погрузкой других автомашин. При этом склад оплачивает предприятиям расходы, связанные с простоем на складе их автомашин и шоферов в очереди под погрузку, из расчета 2,6 у.е. за час простоя автомашины и шофера. Определите:
оптимальное количество необходимых складу кранов, при котором суммарные ожидаемые потери склада, связанные с простоем кранов (из-за отсутствия автомашин) и простоем автомашин в очереди, были минимальными;
коэффициент простоя крана;
среднее число автомашин, находящихся в очереди (длину очереди);
коэффициент и среднее время простоя автомашины в очереди.
Указание : для определения оптимального количества кранов необходимо рассчитать при разном их количестве коэффициенты простоя автомашин в очереди. Например, при четырех кранах коэффициент простоя автомашин будет равен 0,0172, а коэффициент простоя кранов - 0,3299. Тогда потери от простоя кранов и автомашин ( если потер от простоя одного крана равны 5 у.е./ч. , а одной автомашины – 2,6 у.е./ч.) при четырех кранах составят 2,6 *30*0,0172 +5*4*0,3299 = 7,94 у.е. Оптимальное количество кранов будет соответствовать минимальной сумме потерь.
5.1.