3. Задачи нелинейного программирования

(самые трудно решаемые)

Линейное программирование

Рассмотрим стандартную форму задачи линейного программирования:

И рассмотрим каноническую форму

- оптимальное решение

- множество всех оптимальных решений

Задача ЛП разрешима, если множество (иначе неразрешима)

Различают 2 типа неразрешимости:

1. Неразрешимость 1го типа (НР1)

2. Неразрешимость 2го типа (НР2)

(целевая функция не ограничена сверху)

Свойства задач линейного программирования

1. – выпуклое множество

Множество в задаче назовем многогранным, если непусто пересечение конечного числа гиперплоскостей и полуплоскостей

• Гиперплоскость задается уравнением:

• Полупространство задается неравенством:

2. Целевая функция задачи одновременно выпуклая и вогнутая

(любой ее локальный экстремум является глобальным)

ОПРЕДЕЛЕНИЕ

Опорным решение СЛУ называется такое допустимое решение задачи , что положительными координатами соответствует линейно независимые столбцы матрицы A:

Геометрическим образом опорного решения является вершина многогранника

ОПРЕДЕЛЕНИЕ

Базисом опорного решения называется m линейно независимых столбцов, среди которых присутствуют столбцы соответствующие положительным компонентам

ЗАМЕЧАНИЕ

Определение дано в предположении, что

Если , то вычеркиваем линейно зависимые уравнения

Если опорное решение – невырожденное (т.е. ), то получится единственный базис

Если вырожденное ( ), то этому решению соответствует базисы, число которых

СВОЙСТВО

(конечность числа опорных решений)

Число опорных решений СЛУ конечно

ДОКАЗАТЕЛЬСТВО

Из n столбцов можно построить не более чем базисов, следовательно число опорных решений конечно

ТЕОРЕМА

(об экстремуме линейной функции на многогранном множестве (множестве допустимых решений))

Если задача ЛП – разрешима, то целевая функция достигает своего max значения хотя бы на одном опорном решении СЛУ

ДОКАЗАТЕЛЬСТВО

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

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

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

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

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

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

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

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

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

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

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

Получим:

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда

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

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

¤

ВЫВОД

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

ТЕОРЕМА

(о разрешимости задачи ЛП)

Если , а целевая функция ограничена сверху, то задача линейного программирования разрешима (в задачи на max)