Презентация на тему Линейное программирование

Камиля Жордана (1838-1922 гг.), внесший существенный вклад в развитие

алгебры, теории функций и топологии.

+ ai n * xn ,         i = 1, … ,

m              (1.1)
из m линейных форм с n независимыми переменными x1, x2, …,xn. Эта система может быть представлена в виде следующей таблицы:

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

таблицы  аij по определенному алгоритму, а именно с помощью аппарата жордановых исключений.
Пусть, например, возникла необходимость выразить независимую переменную  xs  из уравнения
 
yr  = a r1 * x1 +  a r2 * x2 +  … a rs * xs +  … + a r n * xn ,            (1.4)
 
где yr является переменной, которая  зависит от переменных x1, x2, …, xn, и подставить полученное выражение во все остальные уравнения системы (1.2). Эту операцию можно выполнить по определенной схеме, которая достаточно просто алгоритмизируется.

над таблицей (1.2) с разрешающим элементом  a rs ≠ 0 с  r-ой

разрешающей строкой и  s-ым разрешающим столбцом, схематизированную операцию перемены ролями между зависимой переменной  yr и независимой  xs, т.е. операцию решения уравнения (1.3) относительно xs, подстановки полученного выражения во все остальные уравнения системы (1.1) и записи полученной системы в виде новой таблицы, аналогичной (1.2).

* a r s - a i s * a r  j  ,  (i ≠ r

, j ≠ s )      (1.5)

Причем, как видно из (2.8), все элементы таблицы делятся на разрешающий элемент a rs.

следующей схеме (СХЕМА 1):
1)   разрешающий элемент заменяется единицей и делится

на разрешающий элемент;
2)   остальные элементы разрешающего (s - го) столбца делятся на разрешающий элемент;
3)   остальные элементы разрешающей (s - ой) строки меняют свой знак на противоположный и делятся на разрешающий элемент;
4)   все остальные элементы таблицы вычисляются по формуле (1.5) и делятся на разрешающий элемент a rs;   формула (1.5) иногда называется "правилом прямоугольника", так как схема вычисления элемента bij соответствует вычислению разности произведений элементов, стоящих по основной и побочной диагоналям прямоугольника, образованного в таблице вида (1.2) всеми элементами, вошедшими в формулу (1.5).

x2 – x3
необходимо поменять ролями переменные  x3  и   y2,  т.е.

сделать зависимую переменную y2  независимой,  а независимую переменную x3  зависимой.

шаг обыкновенных жордановых исключений, т.е. заменив переменную x3  на 

y2  по СХЕМЕ 1, изложенной выше, получим следующую таблицу:

Рассмотрим подробнее вычисление последней таблицы, например, коэффициента b31.  Так как разрешающим является элемент a23= 2, то b31 = (a 31 * a 23 - a 21 * a 33) : a 23 = (2 * 2 – ( - 1)* ( - 1) ) : 2 = 3/2 = 1,5 , т.е. была реализована схема:

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

таблице со знаком "минус". В этих случаях имеет смысл вместо обыкновенных использовать так называемые модифицированные жордановы исключения.
Перепишем систему (1.1) в виде эквивалентной ей системы:
    yi  = -ai1*(-x1) -  ai2 *(- x2)-  … - ai n *(- xn) ,             i = 1, …  , m.      
Составим по полученной системе таблицу, учитывая минус при переменных  хj наверху таблицы:

к новой таблице:
 

Эта таблица формируется по СХЕМЕ 2, которая очень напоминает

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

4x3
 запишем в виде таблицы