Шпаргалка по "Математическому программированию"

 

     

16. Переход от канонической формы  модели ЗЛП к стандартной

 

Для перехода от канонической формы к стандартной  можно каждое из

уравнений заменить системой неравенств: 

Другой способ состоит в приведении системы  уравнений к специальному виду и дальнейшему исключению некоторых переменных. 

С помощью  метода Жордана-Гаусса выделяем в каждом уравнении базисную переменную. Такое  выделение осуществляется с помощью  эквивалентных (элементарных) гаусовских преобразований. К ним относятся:

а) умножение  любого уравнения на константу отличную от нуля;

б) прибавление  к любому уравнению любого другого  уравнения, умноженного на любую  константу.

Исходную  систему линейных уравнений перед преобразованием удобно записывать в виде матрицы или таблицы:

Далее находим  х₁, х₂ … х_n . Далее подставляем в целевую функцию z выражениех₁ и х₂ … х_n.

Записываем задачу в стандартной форме. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

17. Понятие гиперплоскости  полуплоскости, опорная гиперплоскость. 

 

18. Геометрич. интерпретация системы ограничений и целевой функции в задачи ЛП

 

 

19. Выпуклое множество: крайние (угловые) точки множества. Выпуклый многогранник

Определение Множество М называется выпуклым, если вместе с любыми двумя точками, принадлежащими данному множеству, оно содержит и отрезок их соединяющий.

 

                        Выпуклое множество

Определение Точка х множества М называется угловой или крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

Теорема 1. Любую точку отрезка можно представить в виде выпуклой комбинации его угловых точек.

х = λ₁ А + λ₂ В

λ₁, λ₂ ≥ 0                выпуклая комбинация точек угловых точек А и В

λ₁ +  λ₂ = 1 

Теорема 2. Любую точку выпуклого замкнутого множества можно представить в виде выпуклой комбинации его угловых точек. 

 

 

20. алгоритм графического метода решения задач ЛП

Алгоритм  графического метода.

1. Проверяется, находится ли исходная ЗЛП в стандартной форме, если нет, то задачу необходимо преобразовать к стандартной форме.

2. Проверяется количество неизвестных переменных. Если это количество больше трёх, то задача не может быть решена графическим методом (существуют другие эффективные методы решения таких задач).

3. Строится область допустимых значений переменных для ЗЛП.

4. Строится направляющий вектор c .

5. Через ОДЗ проводится исходная изоцель (перпендикулярно направляющему вектору).

6. Проводится мысленное перемещение исходной изоцели в направлении вектора c , если определяется максимальное значение целевой функции, или в противоположном направлении, если определяется её минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ и будут оптимальными точками задачи.

7. Для того, чтобы определить координаты оптимальной точки, необходимо решить систему соответствующих линейных уравнений.

8. Для нахождения оптимального значения целевой функции необходимо оптимальные значения переменных подставить в целевую функцию и вычислить её значение. 

20. алгоритм  графич. метода решения задач  ЛП

     Алгоритм  графического метода.

1. Последовательным построением каждого из условий системы ограничений задачи осуществляется построение ОДЗ.
2. Строится направляющий вектор С по коэффициентам при переменных целевой функции.
3. Перпендикулярно направляющему вектору через начало координат проводится исходная изоцель.
4. Проводится мысленное перемещение исходной изоцели в направлении возрастания значений вектора С, если определяется максимальное значение целевой функции или в противоположном направлении, если определяется ее минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ будут оптимальными точками задачи.
5. Для определения координат оптимальной точки необходимо решить систему  соответствующих  линейных уравнений тех условий, на пересечении которых находится оптимальная точка.
6. Для нахождения оптимального значения целевой функции, необходимо координаты  оптимальной точки подставить в целевую функцию и вычислиь ее значение.

 

23. теоремы об области допустимых значений задачи ЛП и о целевой ф-ции 

  Теорема об ОДЗ. Область допустимых решений задачи ЛП выпуклое множество (замкнутое и ограниченное в n-мерном пространстве)

  Теорема 2. О целевой функции  задачи линейного  программирования.

  Целевая функция ЗЛП принимает своё оптимальное  значение в одной из угловых точек  области допустимых значений переменных. Если целевая функция принимает своё оптимальное значение в нескольких угловых точках, то такое же значение она принимает и в любой точке, являющейся выпуклой комбинацией данных угловых точек. 
 

 

24. Теорема об угловой  точке. Достаточное  и необходимое  условие 

 

 

25. Следствия из теоремы  о свойствах решений  задач ЛП и выводы. Понятие опорного плана.

Следствия из теорем.

Определение. План = (х1,х2,…,хn), положительным координатам которого соответствуют линейно независимые векторы, называется опорным планом ЗЛП.

Следствие1. Опорный план имеет не более m положительных координат.

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

Следствие 2. Каждая угловая точка ОДЗ является опорным планом. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

27. Алгоритм симплексного метода.

    При решении задач ЛП симплексным  методом необходимо выполнить следующую  последовательность действий.

1. Проверяется, находится ли задача ЛП в канонической форме. Если нет, то необходимо исходную модель преобразовать в каноническую форму.
2. Выделяется начальный опорный план и значение целевой функции при этом опорном плане.
3. Проводится построение исходной симплексной таблицы.
4. Проверяются значения оценок оптимальности в индексной строке. Если нет положительных оценок, то выписывается оптимальное решение и алгоритм заканчивает свою работу. В противном случае выполняется пункт 5.
5. В базисе вводится вектор, которому соответствует наибольшая положительная оценка. Данный столбец называется разрешающим.
6. Из базиса выводится вектор, которому соответствует симплексное отношение, рассчитанное по формуле          0 < Ө ≤ . Данная строка называется разрешающей строкой.
7. Строится новая симплексная таблица. Соответствующим образом изменяются столбцы Б и С_Б. остальная часть таблицы заполняется из предыдущей с помощью гауссовских преобразований, причем индексная строка считается m+1 строкой и также преобразуется с помощью гауссовских преобразований. Переходим к выполнению пункта 4 данного алгоритма.

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

 

28. выбор базиса и  построение начального  опорного плана  при решении задач  симплекс методом.

 

 

29. Симплекс-таблицы,  их заполнение. Формулы расчета коэффициентов индексной строки.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

30. Теорема оптимальности плана задачи линейного программирования следствие из теоремы оценки оптимальности при решении задач симплекс методом.

    Теорема 1: Если для некоторого вектора Ā_j в системе

Х₁            + а_1m+1X_m+1 + а_1m+2X_m+2 + … + а_1nX_n = a₁

      Х₂      + а_2m+1X_m+1 + а_2m+2X_m+2 + … + а_2nX_n = a₂

…………………………………………………..

          X_m + а_mn+1X_m+1 + а_mn+2X_m+2 + … + а_mnX_n = a_m

    Выполняется соотношение Z_j – c_j > 0, то план Х_Б0 не является оптимальным и можно перейти к плану Х_Б1 такому, что Z (Х_Б1) ≤ Z (Х_Б0).

    Здесь Z_j = (С, Ā_j) – скалярное произведение векторов.

    С – вектор, состоящий из коэффициентов  при базисных переменных целевой  функции Z

    Ā_j – вектор, состоящий из коэффициентов разложения соответствующего вектора по векторам базиса.

    c_j – коэффициент целевой функции Z при переменной Х_j

    Следствие из теоремы: Если для всех векторов Ā₁, Ā₂, …, Ā_n некоторого опорного плана Х выполняется соотношение Z_j – c_j < 0, то опорный план Х является оптимальным. Величины (Z_j – c_j) – называются оценками оптимальности соответствующих векторов.

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

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

 

31. Выбор вектора,  вводящегося в  базис и выводящегося из базиса. Симплексное отношение.

Для перехода к новому опорному плану необходимо один из свободных векторов ввести в базис, а какой-то из базисных векторов вывести. Для введения в базис выберем вектор, имеющий хотя бы одну положительную координату. Пусть таким вектором будет вектор А m+1 .

Разложению  – 

 соотв. вектор, кот. будет  являться опорным планом, если  его координаты будут неотрицательными, а кол-во положительных координат  будет равняться m.

Координаты  вектора Х1 должны быть неотрицательными, т.е. .

Если  , то эта координата будет неотрицательной.

Пусть минимум  в соотношении (5) был получен при i =1, тогда если взять

то первая координата вектора 1 х станет равной нулю.

Соотношение (6) называется симплексным отношением. Таким образом, мы перешли от исходного опорного плана 0 х (базисные векторы А1,А2,…Аm) к опорному плану 1 х (базисные векторы А2,А3,…,Аm,Am+1). 
 

32. разрешающий элемент таблицы, его выбор. Правило полных жордановых исключений для перерасчета симплекс таблицы.

 

33. Правило  «четырехугольника»  для перерасчета  симплекс-таблицы