Исследование операций в экономике
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
Задача 1
Решить графическим методом задачу линейного программирования:
а) найти область допустимых значений (многоугольник решений);
б) найти оптимумы целевой функции.
max и min Z = 2x1 + 4x2
x1 + 3x2 6
x1 + 5x2 5
x1 + x2 6
x1 0, x2 0
Прямые ограничения x1 0, x2 0 означают, что область решений будет лежать в первой четверти декартовой системы координат (рис. 1).
. Множество решений каждого нестрогого неравенства - объединение решений уравнения и строгого неравенства. Заданы уравнения прямых, для построения каждой прямой достаточно двух точек. Удобно строить прямые по точкам пересечения их с осями координат (когда одна из координат равна нулю).
Найдем точки пересечения прямых с осями координат:
Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости. В качестве такой точки удобно брать начало координат. Множества решений 3-го неравенства - полуплоскость, лежащая ниже построенной III-й прямой. Это выясним, взяв контрольную точку, например, (0; 0): 2*0+1*0=0 5. Добавив прямые ограничения, получим многоугольник решений (заштрихованный), обозначим вершины полученного многоугольника решений ABCD.
Координаты этих вершин являются допустимыми решениями данной задачи линейного программирования. Их можно определить, решая систему уравнений двух пересекающихся соответствующих прямых.
Например, точка В - точка пересечения II и III прямых:
б) Приравняем целевую функцию F к постоянной величине а:
x1 + 4x2 = а.
Это уравнение - множество точек, в котором целевая функция принимает значение, равное а. Построим линию уровня при а = 0 (пунктирная прямая): 2x1 + 4x2 = 0.
Точка пересечения этой прямой с осями координат: (0; 0).
При х1 = 1 2*1 + 4*х2 = 0 х2 = 2/4 = 1/2 (1, 1/2).
Для определения направления к оптимуму построим вектор-градиент , координаты которого - частные производные функции F, т.е. = (с1; с2) = (2; 4). Для построения соединим точку (2; 4) с началом координат.
Для нахождения максимума целевой функции смещаем линию уровня параллельно самой себе в направлении вектора-градиента. Максимум достигается в точке A, координаты которой найдем, решая систему уравнений пересекающихся прямых III и x1 =0:
Для определения минимума целевой функции линию уровня смещаем в направлении, противоположном вектору-градиенту. Минимум достигается в точке С, координаты какой найдем, решая систему уравнений пересекающихся прямых 2x1 + 3x2 = 6 и x1 + 5x2 = 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 () = 2x1 + 3x21 + 3x2 18,
x1 + x2 16,2 5, 3х1 21,
x1, x2 0
Решение. Приведем эту задачу к каноническому виду, введя дополнительные переменные х3, х4. х5, х6
Или
Задавая свободным переменным значения х1 = х2 = 0, получим одно из решений данной задачи х1 = 0, х2 = 0, х3 = 18, х4 = 16, х5 = 5, х6 = 21, следовательно, задача обладает исходным опорным планом Х=(0; 0; 18; 16; 5; 21), и для нахождения оптимального плана ее можно решить симплексным методом. Решим эту прямую ЗЛП в симплекс-таблицах:
№ итерацииБазисcjПлан230000Оценка QciА1А2А3А4A5A60А301813100018/3=6А401621010016А5050100105А6021300001F(X)=0-2-30000
В исходной (нулевой) симплекс-таблице в базис всегда вводятся дополнительные векторы, имеющие нулевые коэффициенты. Рассчитаем строку оценок для каждого столбца А1, А2, А3, А4, А5, А6:
?1 = 0*1+ 0*2+0*1+0*0 - 2 = - 2
?2 = 0*3+ 0*1+0*0+0*3 - 3 = - 3
?3 = 0*1+ 0*0+0*0+0*0 - 0 = 0
?4 = 0*0+ 0*1+0*0+0*0 - 0 = 0
?5 = 0*0+ 0*0+0*1+0*0 - 0 = 0
?6 = 0*0+ 0*0+0*0+0*1 - 0 = 0
Исходный опорный план Х=(0; 0; 18; 16; 5; 21) не является оптимальным, так как среди оценок есть отрицательные. Переход к новому опорному плану осуществим, введя в базис новой симплекс-таблицы (итерация 1) вектор А2, имеющий наименьшую отрицательную оценку ?2 = - 3.
Определим вектор, выходящий из базиса нулевой симплекс-таблицы:
,
т.е. вектор А5 следует вывести из базиса. Строка А5 будет направляющей строкой, столбец А2 - направляющим столбцом, и на пересечении их будет находиться разрешающий элемент а32 = 1.
В новой симплекс-таблице (итерация I) в базисе место вектора А5 занимает вектор А2, а векторы А3, A4 и А6 остаются на своих местах. Столбец А2, соответствующий направляющему столбцу, записывается всегда так: на месте разрешающего элемента пишется единица, а все остальные элементы этого столбца - нули. Заполнение столбцов А1, А3, А4, А5, А6 и В производим с помощью формул (а32 = 1 - разрешающий элемент)
№ итерацииБазисcjПлан230000Оценка QciА1А2А3А4A5A6IА3031010-303А40112001-1011/2А235010010А60213000017F(X)=3*5=15-200030
, ,
, ,
Строка А3 :
, , , ,