Часть 5. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Общая постановка задачи
Определение 1. Линейное программирование — наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.
Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.
Определение 2. Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи.
В общем виде математическая модель задачи линейного программирования (ЛП) записывается как
при ограничениях:
где xj — неизвестные; aij, bi, cj — заданные постоянные величины.
Все или некоторые уравнения системы ограничений могут быть записаны в виде неравенств.
Математическая модель в более краткой записи имеет вид
при ограничениях:
Определение 3. Допустимым решением (планом) задачи линейного программирования называется вектор = (x1, x2,..., xп), удовлетворяющий системе ограничений.
Множество допустимых решений образует область допустимых решений (ОДР).
Определение 4. Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным решением задачи линейного программирования и обозначается опт.
Базисное допустимое решение (х1, х2,..., xr, 0, …, 0) является опорным решением, где r — ранг системы ограничений.
Виды математических моделей
Математическая модель задачи ЛП может быть канонической и неканонической.
Определение 5. Если все ограничения системы заданы уравнениями и переменные xj неотрицательные, то такая модель задачи называется канонической.
Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической. Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную xn+i. Если знак неравенства ≤, то балансовая переменная вводится со знаком плюс, если знак неравенства ≥, то — минус. В целевую функцию балансовые переменные не вводятся.
Чтобы составить математическую модель задачи ЛП, необходимо:
— ввести обозначения переменных;
— исходя из цели экономических исследований, составить целевую функцию;
— учитывая ограничения в использовании экономических показателей задачи и их количественные закономерности, записать систему ограничений.
Для рассмотрения решения задач линейного программирования дадим некоторые понятия аналитической геометрии в n-мерном пространстве.
Глава 19. ЭЛЕМЕНТЫ АНАЛИТИЧЕСКОЙ ГЕОМЕТРИИ В n-МЕРНОМ ПРОСТРАНСТВЕ