Материал: 3376

Т е о р е м а 1 (основная теорема линейного программирования). Если каноническая задача линейного программирования имеет оптимальный план, то она имеет и опорный оптимальный план.

Последняя теорема сводит нахождение оптимального плана к нахождению этого плана среди опорных планов, которых конечное число (не больше, чем Cnm ). Достаточно найти все опорные планы и из них выбрать наилучший. Однако обычно числа m и n велики и опорных планов так много, что задача их нахождения очень трудоѐмка. Существует метод (называемый симплексным методом) позволяющий сократить число опорных планов, для которых нужно вычислять значение функции (5.1). Для описания этого метода введѐм следующее понятие.

неизвестных, и система уравнений (9.1) приведена методом Гаусса-Жордана к соответствующему виду (10.1).

Для каждого j ( j m 1, ..., n ) величина

m

j cihij c j i 1

называется оценкой свободной неизвестной x j .

Т е о р е м а 2 (критерий оптимальности невырожденного опорного плана). Для того чтобы невырожденный опорный план был оптимальным, необходимо и достаточно, чтобы оценки всех свободных неизвестных были неотрицательными.

З а м е ч а н и е. Мы рассматриваем задачу на максимум функции (5.1). В случае задачи на минимум этой функции для оптимальности плана оценки свободных неизвестных должны быть неположительными.

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

13

Далее будем считать, что все опорные планы КЗЛП являются невырожденными.

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

Первый шаг: имея невырожденный опорный план, приводим систему ограничений (3.1) методом Гаусса-Жордана к виду, в котором каждая из базисных неизвестных имеет ненулевой коэффициент лишь в одном из

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

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

Четвѐртый шаг: преобразованием Гаусса-Жордана из числа базисных выводится неизвестная с номером ключевой строки и вводится в базис неизвестная с номером ключевого столбца.

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

Затем для полученной системы уравнений повторяем второй шаг и, если это нужно, третий и четвѐртый шаги. И так далее.

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

14

При применении симплексного метода удобно записывать результаты вычислений в так называемую симплексную таблицу (табл. 5.1).

Объясним составление этой таблицы. Во втором столбце Б выписаны базисные неизвестные, в первом С – коэффициенты линейной функции (5.1), стоящие при этих неизвестных. В третьем столбце стоят правые части уравнений, разрешѐнных относительно базисных неизвестных, в следующих – коэффициенты при неизвестных в этих уравнениях. Предпоследний столбец служит для контроля над вычислениями. Указанная в нѐм сумма коэффициентов при неизвестных и правой части уравнений преобразуется по тем же формулам, что и каждое еѐ слагаемое.

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

15

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

Опишем получение последней строки таблицы: в ней записывают оценки

После того как таблица составлена и выбран ключевой элемент hrs , следующий шаг симплексного метода делается так:

1)в первом столбце cr заменяется на cs , во втором xr – на xs ;

2)коэффициенты ключевой строки во всех остальных столбцах, кроме последнего, делятся на hrs ;

3)каждый новый коэффициент в остальных строках вычисляется как определитель второго порядка, у которого в левом верхнем углу записан старый коэффициент, в правом верхнем углу – коэффициент из той же строки и ключевого столбца, в левом нижнем углу – коэффициент из того же столбца и преобразованной ключевой строки, в правом нижнем углу 1 (правило прямоугольника);

4)контролируется правильность вычислений;

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

6. МЕТОД ПОТЕНЦИАЛОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

Пусть имеются пункты A1 , A2 , …, Am отправления однородного груза

то есть общее количество груза, имеющегося в пунктах отправления, равно общей потребности в нѐм в пунктах назначения.

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

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

Все данные удобно занести в транспортную таблицу (табл. 6.1).