Методика преподавания курса "Матричные игры" (стр. 4 из 5)
Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси
(начальная ордината), а угловой коэффициент прямой 
останется постоянным (см.рис.2.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.Вектор
с координатами из коэффициентов ЦФ при 
и 
перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора 
совпадает с направлениемвозрастания ЦФ, что является важным моментом для решения задач. Направлениеубывания ЦФ противоположно направлению вектора .Суть графического метода заключается в следующем. По направлению (против направления) вектора
в ОДР производится поиск оптимальной точки 
. Оптимальной считается точка, через которую проходит линия уровня 
, соответствующая наибольшему (наименьшему) значению функции 
. Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.
Рисунок 2.1 Геометрическая интерпретация ограничений и ЦФ задачи.
Методика решения задач ЛП графическим методом
Если неравенство истинное,
то надо заштриховать полуплоскость, содержащую данную точку;
иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку
и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси 
и правее оси , т.е. в I-м квадранте.Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.
IV. Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня
(где L – произвольное число, например, кратное 
и 
, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.V. Построить вектор
, который начинается в точке (0;0) и заканчивается в точке 
. Если целевая прямая и вектор 
построены верно, то они будут перпендикулярны.VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора
, при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).VII. Определить координаты точки max (min) ЦФ
и вычислить значение ЦФ 
. Для вычисления координат оптимальной точки 
необходимо решить систему уравнений прямых, на пересечении которых находится .Решить задачу линейного программирования
1.f(x)=2x1+x2 ->extr
x1+ x2 <=3
x1+3x2 <=5
5x1-x2 <=5
x1+x2 >=0
x1>= 0, x2>=0
> plots[inequal]({a+b<=3,a+3*b<=5,5*a-b<=5,a+b>=0,a>=0,b>=0}, a=-2..5, b=-2..5, optionsfeasible=(color=red),
optionsopen=(color=blue, thickness=2),
optionsclosed=(color=green, thickness=3),
optionsexcluded=(color=yellow));
> with(simplex):
> C:={ x+y <=3, x+3*y <=5, 5*x-y <=5,x+y >=0};
> dp:=setup({ x+y <=3, x+3*y <=5, 5*x-y <=5,x+y >=0});
> n:=basis(dp);
-display(C,[x, y]);
> f :=2*x+y:
> L:=cterm(C);
> feasible(C, NONNEGATIVE , 'NewC', 'Transform');
-X:=dual(f,C,p);
-R:=maximize(f,C ,NONNEGATIVE );
-f_max:=subs(R,f);
-R1:=minimize(f,C ,NONNEGATIVE );
f_min:=subs(R1,f);
ОТВЕТ: При x1=5/4 x2=5/4 f_max=15/4; При x1=0 x2=0 f_min=0;
Урок № 5.Решение матричных игр, используя методы линейного программирования и симплекс метод
Тип урока: урок контроль + урок изучения нового материала. Вид урока: Лекция.
Продолжительность: 2 часа.
Цели:1)Проверить и закрепить знания по прошедшему материалу на прошлых уроках.
2) Изучить новый метод решения матричных игр.
3) развить память, математическое мышление и внимание.
1 этап: проверить домашнее задание в виде самостоятельной работы.
2 этап: дать краткое описание метода зигзага
3 этап: закрепить новый материал и дать домашнее задание.
Ход занятия.
Методы линейного программирования - численные методы решения оптимизационных задач, cводящихся к формальным моделям линейного программирования.
Как известно, любая задача линейного программирования может быть приведена к канонической модели минимизации линейной целевой функции с линейными ограничениями типа равенств. Поскольку число переменных в задаче линейного программирования больше числа ограничений (n > m), то можно получить решение, приравняв нулю (n - m) переменных, называемых свободными. Оставшиеся m переменных, называемых базисными, можно легко определить из системы ограничений-равенств обычными методами линейной алгебры. Если решение существует, то оно называется базисным. Если базисное решение допустимо, то оно называется базисным допустимым. Геометрически, базисные допустимые решения соответствуют вершинам (крайним точкам) выпуклого многогранника, который ограничивает множество допустимых решений. Если задача линейного программирования имеет оптимальные решения, то по крайней мере одно из них является базисным.
Приведенные соображения означают, что при поиске оптимального решения задачи линейного программирования достаточно ограничиться перебором базисных допустимых решений. Число базисных решений равно числу сочетаний из n переменных по m:
С = m n! / n m! * (n - m)!и может быть достаточно велико для их перечисления прямым перебором за реальное время. То, что не все базисные решения являются допустимыми, существо проблемы не меняет, так как чтобы оценить допустимость базисного решения, его необходимо получить.
Проблема рационального перебора базисных решений задачи линейного программирования была впервые решена Дж. Данцигом. Предложенный им симплекс-метод до настоящего времени является наиболее распространенным общим методом линейного программирования. Симплекс-метод реализует направленный перебор допустимых базисных решений по соответствующим им крайним точкам выпуклого многогранника допустимых решений в виде итеративного процесса, где на каждом шаге значения целевой функции строго убывают. Переход между крайними точками осуществляется по ребрам выпуклого многогранника допустимых решений в соответствии с простыми линейно-алгебраическими преобразованиями системы ограничений. Поскольку число крайних точек конечно, а целевая функция линейна, то перебирая крайние точки в направлении убывания целевой функции, симплекс-метод за конечное число шагов сходится к глобальному минимуму.