Методы решения систем линейных неравенств

Категория реферата: Рефераты по математике
Теги реферата: рынок реферат, отчет по производственной практике
Добавил(а) на сайт: Nazarov.

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

|Б |X1 |X2 |X3 |X4 |X5 |C |
|X3 |-1 |1 |1 |0 |0 |1 |
|X4 |1 |-1 |0 |1 |0 |1 |
|X5 |1 |1 |0 |0 |1 |2 |
|f |-6 |7 |0 |0 |0 |3 |

Для этого выбираем столбец с отрицательным коэффициентом в последней строке[2] (столбец 3) и составляем для положительных элементов данного столбца отношения свободный член/коэффициент (1/1; 2/1)[3]. Из данных отношений выбираем наименьшее и помечаем соответствующую строку[4].

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

|Б |X1 |X2 |X3 |X4 |X5 |C |
|X3 |0 |0 |1 |1 |0 |2 |
|X1 |1 |-1 |0 |1 |0 |1 |
|X5 |0 |2 |0 |-1 |1 |1 |
|f |0 |1 |0 |6 |0 |9 |

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

[pic]

Метод искусственного базиса

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

Суть метода довольно проста:

1. К строкам, в которых отсутствует базисная переменная добавляется по одной искусственной базисной переменной.

2. Новая задача решается Симплекс-методом, причем все искусственные базисные переменные должны стать свободными (выйти из базиса) и их сумма должна равняться нулю, в обратном случае в данной системе невозможно выделить допустимый базис.

Рассмотрим следующий пример:

[pic]

min(f)-?

1. В первом уравнении нет базисных неизвестных. Введём искусственную базисную неизвестную Y1 и заполним первую симплекс-таблицу

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

F=Y1>min

Выражая базисную неизвестную Y1 через свободные получаем:

F+4X1+X2=4 >min

|Б |X1 |X2 |X3 |X4 |Y1 |С |
|Y1 |4 |1 |0 |0 |1 |4 |
|X4 |11 |3 |-5 |-1 |0 |12 |
|F |4 |1 |0 |0 |0 |4 |

Выбираем элемент в ячейке (3;2) и делаем шаг.

|Б |X1 |X2 |X3 |X4 |Y1 |С |
|X2 |4 |1 |0 |0 |1 |4 |
|X4 |-1 |0 |-5 |-1 |-3 |0 |
|F |0 |0 |0 |0 |-1 |0 |

min(f)=0, все коэффициенты в последней строке меньше или равны нулю, следовательно мы перешли к новому естественному базису. Теперь можно решать основную задачу.

Принцип двойственности

Поделитесь этой записью или добавьте в закладки