Методы оптимальных решений 2 вариант контрольная работа

Задача 1. Решить графически задачу из лабораторной работы № 1.

Номер варианта а b с а1 b1 с1.....
2 12 33 20 5 5.....
...

Задача 3. Решить двухкритериальную задачу линейного программирования методом идеальной точки.

Задача 2. Составить двойственную задачу к задаче 1. Найти ее решение по теореме равновесия.

Получаем:5*0+0≥12 не верно. Следовательно отмечаем полуплоскость, не содержащую «пробную» точку (0;0).5*0+4*0≥33 не верно. Следовательно отмечаем полуплоскость, не содержащую «пробную» точку (0;0).2*0+5*0≥20. Следовательно отмечаем полуплоскость, не содержащую «пробную» точку (0;0).Выбранные полуплоскости отметим стрелочками. Найдем пересечение отмеченных полуплоскостей с учётом условия: x1,x2≥0/ Заштрихуем полученный неограниченный четырехугольник ABCDПостроим линию Z=0: 11000x1+1000x2=0 х101 x20-11Вектор grad Z=(11000;1000) определяет направление наибольшего возрастания функции Z.Построим из начала координат вектор N= grad Z1000= (11;1). Этот вектор также показывает направление наибольшего возрастания функции.Перемещая линию уровня параллельным переносом в направлении вектора N, находимпервую точку пересечения уровня и заштрихованного четырёхугольника – точку А. Эта точка является точкой минимума функции.Точка А получается в результате пересечения прямой (1) с координатной прямой X2, где Х1 = 0. Решаем:5х1 + х2 = 12 если уже известно что х1 = 0 5∙0 + 12 = 0 + х2 = 12  х2 = 12 Zmin=Z0,12=11000∙0+1000∙12=12 000Ответ: Для осуществления связи с наименьшими затратами необходимо взять 12 кабелей второго типа, при этом минимальные затраты составят 12 000 у.е.Задача 2. Составить двойственную задачу к задаче 1. Найти ее решение по теореме равновесия. 5x1+x2 ≥125x1+4x2≥332x1+5x2≥20x1,x2≥0Zx1,x2=11000x1+1000x2→minРешение исходной задачи было найдено ранее графическим способом при решении задачи № 1:Zmin(0;12)=12000Составим двойственную задачу.y1y2y35x1+x2 ≥125x1+4x2≥332x1+5x2≥20x1,x2≥0Zx1,x2=11000x1+1000x2→minДвойственная задача x1x25y1+5y2+2y3≥11000y1+4y2+5y3≥1000y1,y2,y3≥0Wy1,y2,y3=12y1+33y2+20y3→maxНайдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей жесткости.y15x1+x2-12=0y25x1+4x2-33=0y32x1+5x2-20=0x1(11000-5y1+5y2+2y3=0x2(1000-y1+4y2+5y3=0Подставим в составленную систему оптимальное решение исходной задачи: X1=0 и X2=12y15∙0+12-12=0y25∙0+4∙12-33=0y32∙0+5∙12-20=00∙(11000-5y1+5y2+2y3=012∙(1000-y1+4y2+5y3=0Произведение равно нулю, если один из множителей равен 0. Получаемy1∙0=0y2∙15=0 ⇒ y2=0y3∙40=0⇒ y3=00∙(11000-5y1+5y2+2y3=012∙(1000-y1+4y2+5y3=0В 4 уравнении первый множитель 0 значит уравнение = 0. Далее 12∙1000-12∙y1+0+0=012y1=12000y1=1000Оптимальное решение двойственной задачи Wmin=W1000;0;0По теореме Zmax=Wmin=12000Окончательно Wmin=W1000;0;0=12000Задача 3. Решить двухкритериальную задачу линейного программирования методом идеальной точки.РешениеПостроим область допустимых решений в плоскости xOy, определяемой системой неравенств. Каждое линейное неравенство на плоскости задает полуплоскость, все точки которой обращают неравенство в верное числовое неравенство.Рассмотрим первое неравенство x-2y≥-8Границей полуплоскости является прямая x-2y=-8. Построим эту прямую по двум точкам (отмечена синим цветом). Составим таблицу x04y46Определим какую полуплоскость задает первое неравенство: выше построенной прямой или ниже её. Для этого подставим в неравенство координаты любой пробной точки, не лежащей на построенной прямой. В качестве «пробной» точки возьмем начало координат (0;0)x-2y≥-80-2∙0≥-80≥-8Получили верное числовое неравенство, значит рассматриваемое линейное неравенство определяет полуплоскость, которой принадлежит начало координат, т.е. расположенную ниже построенной прямой. Аналогично определим полуплоскости, задаваемые вторым и третьим неравенствами: 3x+y≤18 и 3x-2y≤9x04y186x35y03x≥0, y≥0 задают первую координатную четверть.