Математические методы исследования операций в экономике (стр. 4 из 37)

Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:

- ограничения в виде неравенств преобразуются в уравнения за счет добавления фиктивных неотрицательных переменных х_i, (i Î1:m), которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;

- переменные, на которые не наложено условие неотрицательности, представляются в виде разности двух новых неотрицательных переменных:

- = - =

х_j = х_j – х_j, (x_j ≥ 0, х_j ≥ 0).

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

f(x) = 5х₁ + 3x₂ + x₃ + 2х₄ -2х₅ → max

и множеством допустимых планов D, определенным системой уравнений и неравенств,

2х₁	+ 4х₂	+ 5x₃	=7,
- 3x₂	+ 4x₃	– 5x₄ – 4x₅	≤ 2,
3х₁	- 5x₃	+ 6x₄ – 2x₅	≤ 4,
х₁≥ 0,	x₃	≥ 0.

Тогда в соответствии со сформулированными правилами эквивалентная каноническая задача будет иметь вид (D',f'), где:

а множество D' определено как:

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

1.2. ОСНОВНЫЕ СВОЙСТВА ЗЛП И ЕЕ ПЕРВАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ

1.2.1. Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования. Кратко напомним некоторые фундаментальные определения и теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем как линейного, так и нелинейного программирования.

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

Частными случаями линейных пространств являются вещественная прямая, плоскость, геометрическое трехмерное пространство.

Вектор λ₁a¹ + λ₂a² + …+ λ_ma^m называется линейной комбинацией векторов а¹а²,..., а^m с коэффициентами λ₁, λ_2,λ_m,

Система векторов линейного пространства а¹а²,..., а^m называется линейно зависимой, если существуют такие числа λ₁, λ_2,λ_mне равные одновременно нулю, что их линейная комбинация λ₁a¹ + λ₂a² + …+ λ_ma^mравняется нулевому вектору (вектору, все компоненты которого равны нулю). В противном случае систему а¹,а²,..., а^m называют линейно независимой, т. е. линейная комбинация данных векторов может быть равна нулевому вектору только при нулевых коэффициентах λ₁, λ_2,…, λ_m

Максимально возможное количество векторов, которые могут образовывать линейно независимую систему в данном линейном пространстве, называют размерностью пространства, а любую систему линейно независимых векторов в количестве, равном размерности, — базисом пространства.

Линейное пространство обычно обозначают какRⁿ, где n— его размерность.

Любое подмножество данного линейного пространства, которое само обладает свойствами линейного пространства, называется линейным подпространством. Множество Н, получаемое сдвигом некоторого линейного подпространстваL Ì Rⁿ на векторa Î Rⁿ: H=L+a, называется аффинным множеством (пространством). Если фундаментальным свойством любого линейного пространства или подпространства является принадлежность ему нулевого вектора, то для аффинного множества это не всегда так. На плоскости примером подпространства является прямая, проходящая через начало координат, а аффинного множества — любая прямая на плоскости. Характеристическим свойством аффинного множества является принадлежность ему любой прямой, соединяющей две любые его точки. Размерность аффинного множества совпадает с размерностью того линейного подпространства, сдвигом которого оно получено.

Если рассматривается некоторое линейное пространствоRⁿ, то принадлежащие ему аффинные множества размерности 1 называются прямыми, а размерности (n-1)—гиперплоскостями. Так, обычная плоскость является гиперплоскостью для трехмерного геометрического пространства R³, а прямая — гиперплоскостью для плоскости R². Всякая гиперплоскость делит линейное пространство на два полупространства.

Множество V векторов (точек) линейного пространства Rⁿ называется выпуклым, если оно содержит отрезок прямой, соединяющей две его любые точки, или, другими словами, из того, чтоa ÎVи bÎV , следует, что х = (1- λ) х а+ λхbÎV , где 0 ≤λ≤ 1.

Линейная комбинация

векторов а¹,а²... а^mназывается выпуклой, если λ_i ≥0, iÎ1:mи

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

Выпуклая оболочка конечного множества точек называется выпуклым многогранником, а непустое пересечение конечного числа замкнутых полупространств — многогранным выпуклым множеством. В отличие от выпуклого многогранника последнее может быть неограниченным.

Точкаv выпуклого множества V называется его угловой (крайней) точкой, если она не является внутренней точкой ни для какого отрезка, концы которого принадлежат множеству V. Угловые точки выпуклого многогранника являются его вершинами, а сам он — выпуклой оболочкой своих вершин.

Множество К называется конусом с вершиной в точкеx₀, еслиx₀ÎК , и из того, что некоторая точка х принадлежит К ( х Î К ), следует, что в К содержится и луч, начинающийсяв х₀ и проходящий через х, т. е.

или

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

1.2.2. Первая геометрическая интерпретация ЗЛП и графический метод решения. Рассмотрим следующий пример. Пусть дана задача максимизации линейной целевой функции

f(x) = 3х₁ + х₂ → max

на множестве

Так как количество переменных в неравенствах, задающих область допустимых планов задачи, равно двум, то ее можно изобразить на координатной плоскости (см. рис. 1.1).

На рис. 1.1 показано, что каждое неравенство определяет некоторую полуплоскость. Соответствующие области для каждого ограничения отмечены штрихами. Пересечение D данных полуплоскостей (т. е. множество точек, которые одновременно принадлежат каждой их них) является областью допустимых планов задачи. Поведение целевой функции f(x)= 3х₁ + х₂ в рамках двумерной иллюстрации может быть охарактеризовано с помощью линий уровня.

Напомним, что линией уровня функции называется множество точек из ее области определения, в которых функция принимает одно и то же фиксированное значение. Градиентом функцииf(x) называется вектор

Δf(x) = df,…, df

dx₁dx_n

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

Для линейной функции двух переменных линия уровня представляет собой прямую, перпендикулярную вектору с, который служит градиентом данной функции. Следовательно, если линия уровня определяется уравнениемf(x)=c₁x₁+ c₂x₂=const, то этот вектоp имеет вид

и указывает направление возрастания функции.

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