5.10.1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Методы персептрона, релаксаций и Хо — Кашьяпа являются по существу Методами градиентного спуска, приспособленными для решения систем линейных неравенств. Техника линейного программирования сводится к процедурам максимизации или минимизации линейных функций, удовлетворяющих линейному урав- ншию и наложенным на них ограничениям в виде линейных нера- венстэ (заметим, что решение этих неравенств является частью общего решения задачи линейного программирования). В этом разделе будут рассмотрены два возможных подхода к решению таких задач. Для усвоения излагаемого материала от читателя не потребуется никаких предварительных знаний из области линейного программирования, хотя они могли бы оказаться полезными при решении практических задач.

Классическая задача линейного программирования формулируется следующим образом: найти вектор и = (Ыі, ы*. .. .,

который минимизирует линейную целевую функцию  и удовлетворяет ограничению

где а есть {тх іувектор цен, Р — /х 1-вектор и Л—/х/п-матрица.

Для решения поставленной задачи может быть использован симплекс-метод; его описание можно найти в любой книге по линейному программированию. Симплекс-метод представляет собой классическую итеративную процедуру. Его использование требует введения еще одного ограничения для вектора и, а именно

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

где

и

то и а'^, и а“ будут неотрицательны. Отождествляя компоненты и, например, с компонентами а"^ и а~, мы можем наложить ограничение 11^0.