Исследование операций в экономике

Исследование операций в экономике

Задача 1

Решить графическим методом задачу линейного программирования:

а) найти область допустимых значений (многоугольник решений);

б) найти оптимумы целевой функции.

max и min Z = 2x₁ + 4x₂

x₁ + 3x₂ 6

x₁ + 5x₂  5

x₁ + x₂  6

x₁ 0, x₂  0

Прямые ограничения x₁ 0, x₂  0 означают, что область решений будет лежать в первой четверти декартовой системы координат (рис. 1).

. Множество решений каждого нестрогого неравенства - объединение решений уравнения и строгого неравенства. Заданы уравнения прямых, для построения каждой прямой достаточно двух точек. Удобно строить прямые по точкам пересечения их с осями координат (когда одна из координат равна нулю).

Найдем точки пересечения прямых с осями координат:

Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости. В качестве такой точки удобно брать начало координат. Множества решений 3-го неравенства - полуплоскость, лежащая ниже построенной III-й прямой. Это выясним, взяв контрольную точку, например, (0; 0): 2*0+1*0=0 < 6. Множества решений 1-го и 2-го неравенств - полуплоскости, лежащие выше построенных соответственно I-й и II-й прямых. Это выясним, взяв контрольную точку, например, (0; 0): 2*0+3*0=0 > 6, 1*0+5*0=0 > 5. Добавив прямые ограничения, получим многоугольник решений (заштрихованный), обозначим вершины полученного многоугольника решений ABCD.

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

Например, точка В - точка пересечения II и III прямых:

б) Приравняем целевую функцию F к постоянной величине а:

x₁ + 4x₂ = а.

Это уравнение - множество точек, в котором целевая функция принимает значение, равное а. Построим линию уровня при а = 0 (пунктирная прямая): 2x₁ + 4x₂ = 0.

Точка пересечения этой прямой с осями координат: (0; 0).

При х₁ = 1 2*1 + 4*х₂ = 0  х₂ = 2/4 = 1/2 (1, 1/2).

Для определения направления к оптимуму построим вектор-градиент , координаты которого - частные производные функции F, т.е.  = (с₁; с₂) = (2; 4). Для построения  соединим точку (2; 4) с началом координат.

Для нахождения максимума целевой функции смещаем линию уровня параллельно самой себе в направлении вектора-градиента. Максимум достигается в точке A, координаты которой найдем, решая систему уравнений пересекающихся прямых III и x₁ =0:

Для определения минимума целевой функции линию уровня смещаем в направлении, противоположном вектору-градиенту. Минимум достигается в точке С, координаты какой найдем, решая систему уравнений пересекающихся прямых 2x₁ + 3x₂ = 6 и x₁ + 5x₂ = 5:

Ответ: а) заштрихованный многоугольник с угловыми точками А (0; 6); В (4/9; 25/9); С(4/7; 15/7), D(0, 2).

б) max F = 2*0+4*6=24; min F = 2*4/7+4*15/7 =46/7=6.57.

Задание 2

Решить задачу линейного программирования симплексным методом; используя теорию двойственности в анализе оптимальных решений экономических задач найти двойственные оценки; сравнить оптимумы целевых функций взаимодвойственных задач и дать экономическую интерпретацию оптимальных решений этих задач.

max f () = 2x₁ + 3x₂₁ + 3x₂ 18,

x₁ + x₂  16,₂  5, 3х₁  21,

x₁, x₂  0

Решение. Приведем эту задачу к каноническому виду, введя дополнительные переменные х₃, х₄. х₅, х₆

Или

Задавая свободным переменным значения х₁ = х₂ = 0, получим одно из решений данной задачи х₁ = 0, х₂ = 0, х₃ = 18, х₄ = 16, х₅ = 5, х₆ = 21, следовательно, задача обладает исходным опорным планом Х=(0; 0; 18; 16; 5; 21), и для нахождения оптимального плана ее можно решить симплексным методом. Решим эту прямую ЗЛП в симплекс-таблицах:

В исходной (нулевой) симплекс-таблице в базис всегда вводятся дополнительные векторы, имеющие нулевые коэффициенты. Рассчитаем строку оценок  для каждого столбца А₁, А₂, А₃, А₄, А₅, А₆:

∆₁ = 0*1+ 0*2+0*1+0*0 - 2 = - 2

∆₂ = 0*3+ 0*1+0*0+0*3 - 3 = - 3

∆₃ = 0*1+ 0*0+0*0+0*0 - 0 = 0

∆₄ = 0*0+ 0*1+0*0+0*0 - 0 = 0

∆₅ = 0*0+ 0*0+0*1+0*0 - 0 = 0

∆₆ = 0*0+ 0*0+0*0+0*1 - 0 = 0

Исходный опорный план Х=(0; 0; 18; 16; 5; 21) не является оптимальным, так как среди оценок есть отрицательные. Переход к новому опорному плану осуществим, введя в базис новой симплекс-таблицы (итерация 1) вектор А₂, имеющий наименьшую отрицательную оценку ∆₂ = - 3.

Определим вектор, выходящий из базиса нулевой симплекс-таблицы:

,

т.е. вектор А₅ следует вывести из базиса. Строка А₅ будет направляющей строкой, столбец А₂ - направляющим столбцом, и на пересечении их будет находиться разрешающий элемент а₃₂ = 1.

В новой симплекс-таблице (итерация I) в базисе место вектора А₅ занимает вектор А₂, а векторы А₃, A₄ и А₆ остаются на своих местах. Столбец А₂, соответствующий направляющему столбцу, записывается всегда так: на месте разрешающего элемента пишется единица, а все остальные элементы этого столбца - нули. Заполнение столбцов А₁, А₃, А₄, А₅, А₆ и В производим с помощью формул (а₃₂ = 1 - разрешающий элемент)

,  ,  

, ,

Строка А₃ :

, , , ,

.

Строка А₄:

, , , ,

.

Строка А₆ остается без изменений, т.к. там и так .

Получили еще одно решение задачи: х₁ = х₅ = 0, т.к. векторов А₁, А₅ нет в базисе первой итерации, и х₂ = 5, х₃ = 3, х₄ = 11 х₆ = 21, т.к. векторы А₂, А₃, А₄ и А₆ находятся в базисе и им соответствуют значения плана В (5; 3; 11; 21), значит, задача обладает новым опорным планом Х=(0; 5; 3; 11; 0; 21).

Рассчитаем строку оценок  для каждого столбца А₁, А₂, А₃, А₄, А₅, А₆:

∆₁ = 0*1+ 0*2+3*0+0*3 - 2 = -2

∆₂ = 0*0+ 0*0+3*1+0*0 - 3 = 0

∆₃ = 0*1+ 0*0+3*0+0*0 - 0 = 0

∆₄ = 0*0+ 0*1+3*0+0*0 - 0 = 3

∆₅ = 0*(-3)+ 0*(-1)+3*1+0*0 - 0 = 0

∆₆ = 0*0+ 0*0+3*0+0*1 - 0 = 0

Найденный опорный план Х=(0; 5; 3; 11; 0; 21) не является оптимальным, так как среди оценок есть отрицательные. Переход к новому опорному плану осуществим, введя в базис новой симплекс-таблицы (итерация II) вектор А₁, имеющий наименьшую отрицательную оценку ∆₁ = - 2.

Определим вектор, выходящий из базиса нулевой симплекс-таблицы:

,

т.е. вектор А₃ следует вывести из базиса.

Строка А₃ будет направляющей строкой, столбец А₁ - направляющим столбцом, и на пересечении их будет находиться разрешающий элемент а₃₁ = 1. В новой симплекс-таблице (итерация II) в базисе место вектора А₃ занимает вектор А₁, а векторы А₂, A₄ и А₆ остаются на своих местах. Столбец А₁, соответствующий направляющему столбцу, записывается всегда так: на месте разрешающего элемента пишется единица, а все остальные элементы этого столбца - нули. Заполнение столбцов А₂, А₃, А₄, А₅, А₆ и В производим с помощью формул (а₃₁ = 1 - разрешающий элемент).

Получили еще одно решение задачи: х₃ = х₅ = 0, т.к. векторов А₃, А₅ нет в базисе первой итерации, и х₁ = 3, х₂ = 5, х₄ = 5, х₆ = 12, т.к. векторы А₁, А₂, А₄ и А₆ находятся в базисе и им соответствуют значения плана В (3; 5; 5; 12), значит, задача обладает новым опорным планом Х=(3; 5; 0; 5; 0; 12).

Рассчитаем строку оценок  для каждого столбца А₁, А₂, А₃, А₄, А₅, А₆:

∆₁ = 2*1+ 0*0+3*0+0*0 - 2 = 0

∆₂ = 2*0+ 0*0+3*1+0*0 - 3 = 0

∆₃ = 2*1+ 0*(-2)+3*0+0*(-3) - 0 = 1

∆₄ = 2*0+ 0*1+3*0+0*0 - 0 = 0

∆₅ = 2*(-3)+ 0*5+3*1+0*9 - 0 = -6+3= -3

∆₆ = 2*0+ 0*0+3*0+0*1 - 0 = 0

Найденный план Х=(3; 5; 0; 5; 0; 12) не является оптимальным, так как среди оценок есть отрицательные. Переход к новому опорному плану осуществим, введя в базис новой симплекс-таблицы (итерация III) вектор А₅, имеющий наименьшую отрицательную оценку ∆₅ = - 3.

Определим вектор, выходящий из базиса нулевой симплекс-таблицы:

,

т.е. вектор А₄ следует вывести из базиса. Строка А₄ будет направляющей строкой, столбец А₅ - направляющим столбцом, и на пересечении их будет находиться разрешающий элемент а₂₅ = 5.

В новой симплекс-таблице (итерация III) в базисе место вектора А₄ занимает вектор А₅, а векторы А₁, A₂ и А₆ остаются на своих местах. Столбец А₅, соответствующий направляющему столбцу, записывается всегда так: на месте разрешающего элемента пишется единица, а все остальные элементы этого столбца - нули. Заполнение столбцов А₁, А₂, А₃, А₄, А₆ и В производим с помощью формул (а₂₅ = 5 - разрешающий элемент).

Получили еще одно решение задачи: х₃ = х₄ = 0, т.к. векторов А₃, А₄ нет в базисе первой итерации, и х₁ = 6, х₂ = 4, х₅ = 1, х₆ = 3, т.к. векторы А₁, А₂, А₅ и А₆ находятся в базисе и им соответствуют значения плана В (6; 4; 1; 3), значит, задача обладает новым опорным планом Х=(6; 4; 0; 0; 1; 3).

Рассчитаем строку оценок  для каждого столбца А₁, А₂, А₃, А₄, А₅, А₆:

∆₁ = 2*1+ 0*0+3*0+0*0 - 2 = 0

∆₂ = 2*0+ 0*0+3*1+0*0 - 3 = 0

∆₃ = 2*(-1/5)+ 0*(-2/5)+3*2/5+0*(3/5) - 0 = 4/5

∆₄ = 2*3/5+ 0*1/5+3*(-1/5)+0*(-9/5) - 0 = 0

∆₅ = 2*0+ 0*1+3*0+0*0 - 0 = -6+3= 0

∆₆ = 2*0+ 0*0+3*0+0*1 - 0 = 0

Новый план Х=(6; 4; 0; 0; 1; 3) - оптимальный, так как в строке оценок ∆_j нет отрицательных значений.

Находим оптимум целевой функции:

max f() = 2 x₁ + 3x₂ = 2*6 + 3*4 = 24.

Найдем двойственные оценки.

Расширенная матрица коэффициентов при неизвестных в системе ограничений исходной задачи а_ij и свободных членов b_i; коэффициенты целевой функции:

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

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

Для нахождения оценок у₁, у₂, у_3, y₄ используем вторую теорему двойственности.

Проверим, как удовлетворяется система функциональных ограничений оптимальным планом

Поскольку третье и четвертое ограничение в (*) выполняется как строгое неравенство, то у₃ =0 и y₄=0. Так как х₁>0, х₂> 0, то оба неравенства из двойственной задачи выполняются как равенства:

,

,

Т.е.    

Z(1, 0, 1, 0)= 18*4/5+16*3/5+5*0+21*0=(72+48)/5=24.

оптимум линейный программирование двойственный симплексный

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

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

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

В задаче увеличение ресурса I вида на 1 ед. привело бы к росту максимальной суммы прибыли на 4/5 у.е. (у₁=1), а увеличение ресурса III и IV вида не повлияет на оптимальный план выпуска продукции и сумму прибыли (y₃, y₄ = 0).

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

В задаче недефицитными являются ресурс III и IV поскольку у₃=0, y₄ =0.

Острее ощущается дефицитность ресурса I (у₁=4/5) - он более дефицитен, чем ресурс II (y₂ = 3/5).