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

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

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

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

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

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

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

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

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

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

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

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

1. Последовательным построением каждого из условий системы ограничений задачи осуществляется построение ОДЗ.

2. Строится направляющий вектор С по коэффициентам при переменных целевой функции.

3. Перпендикулярно направляющему вектору через начало координат проводится исходная изоцель.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Проводится построение исходной симплексной таблицы.

4. Проверяются значения оценок оптимальности в индексной строке. Если нет положительных оценок, то выписывается оптимальное решение и алгоритм заканчивает свою работу. В противном случае выполняется пункт 5.

5. В базисе вводится вектор, которому соответствует наибольшая положительная оценка. Данный столбец называется разрешающим.

6. Из базиса выводится вектор, которому соответствует симплексное отношение, рассчитанное по формуле 0 < Ө ≤ . Данная строка называется разрешающей строкой.

7. Строится новая симплексная таблица. Соответствующим образом изменяются столбцы Б и С_Б. остальная часть таблицы заполняется из предыдущей с помощью гауссовских преобразований, причем индексная строка считается m+1 строкой и также преобразуется с помощью гауссовских преобразований. Переходим к выполнению пункта 4 данного алгоритма.

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

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