17.Постановка задачи. Входная, выходная информация. Алгоритм решения задачи.

Постановка задачи – это точная формулировка решения задачи на компьютере с описанием входной и выходной информации, т.е. определение целей или назначение задачи, ее место и связи с другими задачами; условия решения задачи с использованием средств вычислительной техники; состав и форма представления выходной информации; источники входной информации для решения задачи и т.п.

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

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

Алгоритмы решения

Симплекс-метод для решения задач линейного программирования считается наиболее известным и широко применяемым на практике. Симплекс-метод является достаточно эффективным алгоритмом. Он показывает хорошие результаты при решении прикладных задач в области линейного программирования, он является алгоритмом сэкспоненциальной сложностью.

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

В 1979 году математиком Л. Хачияном был предложен метод эллипсоидов, который разрешил проблему, остававшуюся нерешённой долгое время. Этот метод имеет совершенно другую, некомбинаторную, природу, в отличии симплекс-метода. Недостаток данного метода в том, что в вычислительном плане он оказывается неперспективным. Факт полиномиальной сложности задач способствовал к внедрению целого класса эффективных алгоритмов линейного программирования. Один из методов - это метод внутренней точки, предложенный в 1984 году Н. Кармаркаром, . Алгоритмы метода внутреней точки используют непрерывную трактовку задачи линейного программирования. В отличии от симплекс-метода, метод внутренних точек обходит точки из внутренней части области допустимых значений и использует методы логарифмических барьерных функций нелинейного программирования, которые были разработаны в 1960-х гг. Фиако (Fiacco) и МакКормиком (McCormick).