§ 1. Основные понятия и определения
Математическое программирование представляет собой математическую дисциплину, занимающуюся теорией и методами решения многомерных экстремальных задач на множествах, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).
В общем виде задача математического программирования формулируется следующим образом: найти наименьшее (или наибольшее) значение функции при ограничениях
где и – заданные функции, а – некоторые постоянные числа.
В зависимости от свойств функции и математическое программирование делится на ряд самостоятельных дисциплин. Прежде всего это линейное программирование. К задачам линейного программирования (ЛП) относятся задачи математического программирования, в которых функции и
Для решения задач линейного программирования существуют универсальные методы, с помощью которых можно решить любую задачу линейного программирования.
Рассмотрим основную задачу линейного программирования.
Пусть заданы линейная функция
(1.1)
и система линейных уравнений с неизвестными
(1.2)
где , и – заданные постоянные числа.
Необходимо среды неотрицательных решений системы (1.2) найти такое решение, при котором функция (1.1) принимает минимальное значение.
Сформулированная задача называется канонической или основной задачей линейного программирования (ЗЛП).
Условия неотрицательности решения системы (1.2), если они не оговорены в формулировке задачи, записываются в виде
. (1.3)
Функцию (1.1) называют целевой функцией (ЦФ), а условия (1.2) – ограничениями-равенствами.
Всякое неотрицательное решение системы (1.2) называется допустимым решением или планом задачи.
Совокупность допустимых решений системы (1.2) называется областью допустимых решений (ОДР).
Допустимое решение системы (1.2), минимизирующее функцию (1.1), называется оптимальным решением или оптимальным планом ЗЛП.
Значение целевой функции (1.1), отвечающее оптимальному решению, называется оптимумом.
Если в задаче линейного программирования необходимо найти максимум функции , то максимизацию этой функции можно заменить минимизацией противоположной функции .
Рассмотрим другую задачу линейного программирования.
Пусть заданы линейная функция
(1.4)
и система линейных уравнений с неизвестными
(1.5)
где , и – заданные постоянные числа.
Необходимо среды неотрицательных решений системы (1.5) найти такое решение, которое минимизирует функцию (1.4).
Сформулированная задача называется стандартной или симметричной задачей линейного программирования.
Условия (1.5) называются ограничениями-неравенствами.
Стандартную задачу линейного программирования нетрудно привести к каноническому виду, заменив неравенства в системе (1.5) равенствами с помощью введения новых неотрицательных неизвестных .