--PAGE_BREAK--
10.Общая форма модели задач ЛП и ее особенности
Общая форма ЗЛП имеет вид:
Найти максимум или минимум целевой функции z:
z = С1x1 + … + Сnxn max (min)
При выполнении следующих ограничений:
а11X1+ a12 X2 + … + а1n Xn R1 a1
а21X1+ a22 X2 + … + а2n Xn R2 a2
………………………………………………….
am1X1 + аm2 X2 +…+ аmnxn Rm am
хj ≥ 0, j = 1, k, k≤n
В общей форме каждый символ R1 , R2 ,…, Rm означает один из знаков: ≥, = или ≤.
Общая форма модели задачи ЛП обладает следующими особенностями.
1. Система ограничений представлена в виде уравнений (жестких условий) и неравенств (нежестких условий).
2. Условия неотрицательности накладываются не на все переменные
3. Целевая функция стремится либо к максимуму, либо к минимуму.
--PAGE_BREAK--
Следствие 2. Каждая угловая точка ОДЗ является опорным планом.
27. Алгоритм симплексного метода.
При решении задач ЛП симплексным методом необходимо выполнить следующую последовательность действий.
1. Проверяется, находится ли задача ЛП в канонической форме. Если нет, то необходимо исходную модель преобразовать в каноническую форму.
2. Выделяется начальный опорный план и значение целевой функции при этом опорном плане.
3. Проводится построение исходной симплексной таблицы.
4. Проверяются значения оценок оптимальности в индексной строке. Если нет положительных оценок, то выписывается оптимальное решение и алгоритм заканчивает свою работу. В противном случае выполняется пункт 5.
5. В базисе вводится вектор, которому соответствует наибольшая положительная оценка. Данный столбец называется разрешающим.
6. Из базиса выводится вектор, которому соответствует симплексное отношение, рассчитанное по формуле 0 . Данная строка называется разрешающей строкой.
7. Строится новая симплексная таблица. Соответствующим образом изменяются столбцы Б и СБ. остальная часть таблицы заполняется из предыдущей с помощью гауссовских преобразований, причем индексная строка считается m+1 строкой и также преобразуется с помощью гауссовских преобразований. Переходим к выполнению пункта 4 данного алгоритма.
После построения каждой таблицы можно проверить правильность вычислений с использованием формул вычисления оценок, приведенных в предыдущем параграфе.
--PAGE_BREAK--
47. расчет оценок оптимальности распределения транспортных задач и критерий оптимальности.
Исходя из соотношения б) теоремы можно записать следующую формулу для вычисления оценок: δ ij = ui +vj – сij. Для того, чтобы оценки не перепутать с объёмами перевозок, они (оценки) заключаются в круги.
Оценки оптимальности в свободных клетках ТЗ представляют собой критерий оптимальности, с помощью которого осуществляется проверка распределения на оптимальность. Если оценки всех свободных клеток меньше или равны нулю, то данное распределение является оптимальным.
--PAGE_BREAK--