Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата

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

Замечание: Если переменная хк не подчинена условию не отрицательности, ее нужно заменить на разность двух не отрицательных величин xk = uk + vk .

Определение: Совокупность не отрицательных чисел х1, х2,..., хn , удовлетворяющих ограничениям задачи, называются допустимым решением или просто планом задачи.

План Х* = (х1*, х2*, ..., хn*) при котором целевая функция достигает своего экстремального значения, называется оптимальной.

Не нулевые допустимые решения задачи, называются базисными решениями, если соответствуют им векторы (Аj образуют линейно не зависимую систему.

2 Симплекс - метод .

С самого начала укажем, что симплекс-метод в его непосредственной форме предназначен для решения канонической задачи линейного программирования.

Для работы по симплекс-методу требуется:

1. привести задачу к канонической форме;

2. представить ее в векторной форме;

3. заполнить первую симплексную таблицу;

4. проверить план на оптимальность;

5. если план не оптимален, то выбрать разрешающий элемент, произвести пересчет всех элементов симплексной таблицы и перейти к п.4

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

Для построения первой таблицы из векторов (Аj нужно выбрать несколько компонентов, которые образуют единичную матрицу[pic]. И если исходная система ограничений, содержит только неравенства ( или (, то при введении дополнительных переменных, сразу получают базисные векторы, которые образуют первый базис в симплекс-таблицах.

|Сб |Хб |план |С1 |С2 |..... |Сn |
| | | | | | | |
| | | |х1 |х2 |.... |хn |
| | | | | | | |
| | | | | | | |
| | | | | | | |
|(j | |(0 |(1 |(2 |... |(n |

В верхней строке записывают коэффициенты при переменных целевых функций. В столбцы х1, х2, ..., хn - заносят элементы векторов (А1,
(А2,(Аn. В столбец план - заносят компоненты вектора (В. Столбец Хб - отображает переменные входящие в базис. Их индексы совпадают с индексами базисных векторов. Столбец Сб - коэффициенты при базисных переменных в целевой функции.

Проверка плана на оптимальность. Нижняя строка симплекс-таблицы (j - называется индексной.

(0 = (Сб *(В;

(j = (Сб*(хj - Сj или (j = (Cб *(Аj - Cj

Она служит для проверки опорного плана на оптимальность. Если все (j (
0, то все планы являются оптимальными.

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

1. В качестве разрешающего столбца выбирают столбец для которого элемент индексной строки (р является самым маленьким отрицательным числом.

2. Находим отношения компонент столбца план к неотрицательным элементам разрешающего столбца.

3. Выбираем наименьшее из данных отношений. Строка с ним называется разрешающей.

Рекомендуем скачать другие рефераты по теме: шпоры по гражданскому праву, заказать дипломную работу.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата