6.Симплексные преобразования. Опорные решения системы линейных уравнений

любое неотрицательное базисное решение явл. опорным. Опорных решений меньше, чем базисных, но любое опорное явл. базисным.

-система приведена к ед базису

-все свободные члены >=0

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

- он должен быть >0

- составляют отношение свободных членов к +элементам разрешающегося столбца

Среди этих отношений выбираем min и уравнение которое ему соответствует называется разрешающим.

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

14.Задача целочисленного программирования. Метод Гомори.

Из системы ограничений выбираем уравнение для которого дробная часть (координаты оптимального решение) имеет наибольшее значение и на его основе составляются дополнительные ограничения, которые отсекает от области ДР не целочисленные оптимальные решения, но при этом сохраняет целочисленные вершины этой области. Пусть i-гор задачи, находящийся в посл симплексной таблице имеет вид.

X_i- базисные переменные

A_ij – коэф свободных элементов

X_j – свободные переменные

X_j^*- правая часть уравнения, коор опт решения, которые явл дробными членами

Тогда дополнительное ограничение

Q_i^*- дробная часть x_i^*

Q_ij- дробная часть a_ij

Дробная часть q >=a,но <1

В уравнение * вводится дополнительная переменная

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

7. Алгоритм решения злп графическим методом

1. ОДЗ или ОДР многоугольник планов

2. Строим вектор нормаль n (c₁,C₂), с точкой преломления в начале координат

3. Перпендикулярно n строится линия уравнения L?пересекающая многоугольник планов

4. Линия уровня перемещается самой себе в направлении, совпадающим с направлением вектора n в зад. На max, и в противоположную сторону на min. До положения крайних точек ОДЗ.

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

6. Подставляем эти координаты в целевую функцию. Вычисляем оптимальное решение

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

8. В случае неограниченной области max(min) значение либо не существует, если многоугольник планов не ограничен сверху(снизу), либо достигает по крайней мерее в одной из вершин

9. Если применить графический метод вместе с методом Ж-Г, то этим методом можно решать задачи, где кол-во неизвестных больше 2-х. при этом должно выполняется условие:

- число неизвестных должно быть больше числа уравнений равно на 2, т.е. n-m=2

- решаем следующим образом

1. Систему приводим к ед базису. Базисные переменные отбрасываем, при этом систему уравнений приводим к системе нер-в, содержащих 2 неизвестные

2. Решаем графическим методом

3. Базисные переменные искл. Из целевой функции , для этого коэффициенты целевой функции записывают в таблицу Ж-Г в последнею строку, как коэффициент некоторого дополнительного уравнения с правой частью =-C₀

Графическое изображение целевой функции