ДОКАЗАТЕЛЬСТВО. Рассмотрим задачу в канонической форме ( задача сводится к канонической)

Рассмотрим задачу в канонической форме ( задача сводится к канонической)

По условию, задача разрешима, те

Выберем любое оптимальное решение

1) Если оно является опорным ч.т.д

2) не является опорным

Будем считать, что первые k координат положительные

Но т.к. - не является опорным решением, то

Следовательно cсуществуют отличные от нуля

Всегда будем считать, что есть такие, что не равны нулю.

Но с другой стороны существует нетривиальное решение системы уравнений , а т.к. оно однородное, то существует решение с точностью до знака

Допишем к системе (2) уравнение

Получим:

Решение системы:

Теперь определим так, чтобы

Получим общее решение данной системы:

– всегда конечное положительное число (т.к. есть всегда)

– величина отрицательная (может быть )

Учитывая однородность (2), можно утверждать, что (*)

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

Заметим, что оно имеет меньше чем положительных компонент.

Докажем, что все эти решения являются оптимальными

Для этого докажем, что

Рассмотрим целевую функцию:

Из неравенства получаем, что

Т.к. на принимает как положительные, так и отрицательные значения, то

Тогда

Следовательно – оптимальное решение задачи.

Итерируя описанный процесс преобразования , через конечное число итераций получим оптимальное опорное решение.

¤

ВЫВОД

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

Поиск по сайту: