Основные понятия линейного программирования

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

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

Математически задача линейного программирования формируется следующим образом: требуется найти абсолютный экстремум (наименьшее или наибольшее значение в зависимости от смысла задачи) линейной функции.

; (1).

• (целевая функция) при условии, что на переменные x₁, x_2, …x_n наложены ограничения в виде равенств или неравенств:
• () ()(2)

(3).

Определение 1. Максимальная совокупность значений х₁, х₂, …, х_n, удовлетворяющих всем неравенствам (2) и (3), называется область допустимых значений задачи линейного программирования (короче, допустимой областью).

Допустимая область задачи линейного программирования представляет собой выпуклый многогранник (возможно, являющийся пустым множеством, если система неравенств (1), (3) невозможна).

Определение 2. Набор значений х₁, х₂, …, х_n, из допустимой области, при которых целевая функция (1) принимает, по смыслу задачи, или наименьшее или наибольшее значение, называется решением задачи линейного программирования (или оптимальный план). В случае существования хотя бы одного решения задача линейного программирования называется разрешимой. [1].

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

В самом общем виде задача математически записывается так:

U = f (x) -> max; X W ,(4.1).

где X = (x₁, х₂ …, х_п)

W — область допустимых значений переменных х₁, х₂, …, х_п.

F (x) — целевая функция.

Для того чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т. е. указать Х₀ W такое, что f (x₀) >f(x) при любом X W_, или для случая минимизации —f (x₀) при 1 любом X W.[3].

Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешима, если целевая функция f (x) не ограничена сверху на допустимом множестве W.

Методы решения оптимизационных задач зависят как от вида целевой функции f (x), так и от строения допустимого множества W. Если целевая функция в задаче является функцией п переменных, то методы решения называют методами математического программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f (х) и от области W:

задачи линейного программирования, если f[х) и W линейны;

задачи целочисленного программирования, если ставится условие целочисленности переменных х₁, х₂, …, х_п;

задачи нелинейного программирования, если форма f (x) носит нелинейный характер. [4].

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

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

f (x) = c_j x_j max (min);(4.2).

,; (4.3).

(4.4).

; (4.5).

При этом система линейных уравнений (4.3) и неравенств (4.4), (4.5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f (X) называется целевой функцией, или критерием оптимальности.

В частном случае, если I = 0, то система (4.3) — (4.4) состоит только из линейных неравенств, а если I= M, то — из линейных уравнений.

Если математическая модель задачи линейного программирования имеет вид:

(4.6).

;(4.7).

(4.8).

то говорят, что задача представлена в канонической форме. [6].

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

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

если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

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

если некоторая переменная х_к не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными где — свободный индекс, [4].