Геометрическая интерпретация злп доклад

Обновлено: 05.07.2024

Аннотация: Предмет дискретного программирования. Постановка задачи линейного программирования. Геометрическая интерпретация задачи линейного программирования. Общий путь нахождения оптимального плана. Вычислительные методы линейного программирования. Пример математической модели дискретного программирования (транспортная задача). Метод северо-западного угла.

Предмет дискретного программирования

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

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

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

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

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

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

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

( 6.1)

где — - — известные коэффициенты ;

- - — неизвестные переменные .

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

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

$a_<11>x_1+a_x_2+. +a_x_j+. +a_x_n=b_1;\\ a_x_1+a_x_2+. +a_x_j+. +a_x_n=b_2;\\ . \\ a_x_1+a_x_2+. +a_x_j+. +a_x_n=b_i;\\ a_x_1+a_x_2+. +a_x_j+. +a_x_n=b_m;\\$

( 6.2)

Искомые величины не могут быть отрицательными; ,b_i" />
— известные постоянные величины, характеризующие условия задачи.

Целевая функция задается в виде такой линейной формы :

( 6.3)

где — постоянные коэффициенты , которые обычно называют коэффициентами стоимости .

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

можно привести систему линейных ограничений к виду (6.2.).

Геометрическая интерпретация задачи линейного программирования

Геометрическую интерпретацию задачи линейного программирования рассмотрим на примере.

Пример

Четыре вида овощей необходимо распределить по шести транспортным средствам .

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

$\left. \begin 4x_1+x_4=16;\\ 2x_2+x_5=10;\\ x_3+2x_4+6x_5=76;\\ 4x_1+3x_2+x_6=24;\\ x_j\ge 0(j=1. 4)\\ \end \right\>$

( 6.4)

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

Последнее условие говорит о том, что число типов транспортного средства не может быть отрицательным.

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

Оплата за конкретное транспортное средство (в тысячах рублей) задана следующей таблицей.

В соответствии с приведенными данными, целевая функция, подлежащая оптимизации, примет вид:

y=0,4x_1+0,5x_2+0,2x_3+0,8x_4+0,6x_5+0,3x_6

( 6.5)

Решение задачи сводится к выполнению ограничений, заданных уравнением (6.4.)

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

Геометрическая интерпретация задачи линейного программирования. Чтобы иметь возможность наглядно представить ограничения и целевую функцию на графике, необходимо выразить все неизвестные через две независимые величины, например, и , соответствующие координатным осям, относительно которых будет производиться построение (рис. 6.1). Из уравнения (6.4.) следует:

$\left. \begin x_3=8x_1+12x_2-16;\\ x_4=16-4x_1;\\ x_5=10-2x_2;\\ x_6=24-4x_1-3x_2 \end \right\>$

( 6.6)

А целевая функция примет такой вид:

$x_j\ge 0$

Из сопоставления уравнений (6.6.) и последнего из ограничений (6.2.) следует:

$x_1\ge 0;\\ x_2\ge 0;\\ x_3=8x_1+12x_2-16\ge 0;\\ x_4=16-4x_1\ge 0;\\ x_5=10-2x_2\ge 0;\\ x_6=24-4x_1-3x_2\ge 0;$

( 6.8)

Каждому из неравенств (6.8.) на графике рис. 6.1 соответствует полуплоскость, в пределах которой находятся все допускаемые данным неравенством значения переменной величины .

Так, например, неравенству соответствует полуплоскость вправо от оси (граница ее заштрихована).

$x_3=8x_1+12x_2 -16\ge 0$

соответствует полуплоскость вправо и вверх от линии, соответствующей значению данного неравенства (при ).

Уравнение этой линии

$x_1+\frac<3></p> <p>x_2-1=0$
.

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

Неравенствам (6.8.) соответствует некоторая область – шестиугольник , образованный границами упомянутых выше полуплоскостей. Эта область может быть названа областью допустимых планов , поскольку любая точка в ее пределах отвечает требованиям наложенных ограничений (6.4.).

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

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

Интересующая нас прямая , как видно из рисунка 6.1, имеет наклон вправо от оси . Задаваясь различными значениями , получим семейство прямых линий, параллельных прямой , которая проходит через точку 0. При этом чем меньше будет , тем, очевидно, правее располагается соответствующая прямая.

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

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

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

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

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

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

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

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

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

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

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

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

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

векторов а 1 , а 2 . а 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)=c₁x₁+ c₂x₂ =const, то этот вектоp имеет вид

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

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

На рис. 1.1 изображен некоторый частный случай, для которого решение ЗЛП достигается в угловой точке х* = (0, 6) области D. Нетрудно представить, что возможны и другие варианты. Они изображены на рис. 1.2.

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

В случае, изображенном на рисунке (b), линия уровня, соответствующая максимальному значению f(x), касается грани множества D, и, соответственно, все точки, лежащие на этой грани, являются оптимальными планами.

Во всех рассмотренных иллюстрациях допустимые планы ЗЛП представлялись в виде некоторого многогранного выпуклого множества на плоскости. Такое их представление в литературе получило название первой геометрической интерпретации задачи линейного программирования.

Заметим также, что аналогичным образом могут быть построены интерпретации ЗЛП для случая трехмерного пространства R 3 , где множеству D будет соответствовать некоторый ограниченный или неограниченный многогранник, а поведение целевой функции будет характеризоваться поверхностями (плоскостями) уровня.

Несмотря на свою очевидную ограниченность, графический метод решения ЗЛП часто оказывается полезным. В частности, он может быть применен не только к задачам с двумя переменными и ограничениями в виде неравенств, но и к каноническим задачам вида (1.7), у которых n - m = 2, где n — количество переменных, а m — ранг матрицы А.

Действительно, можно выбрать две произвольные переменные х_j₁,x_j₂ и, используя систему уравнений, выразить через них остальные переменные

Подставив выражения (1.9) в целевую функцию, мы получим эквивалентную задачу

Последняя ЗЛП может быть решена графически.

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

Теорема 1.1. Если целевая функция f принимает максимальное значение в некоторой точке множества допустимых планов D, то она принимает это значение и в некоторой угловой точке данного множества.

Доказательство.

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

Для доказательства воспользуемся следующим известным свойством ограниченных выпуклых множеств:

Если D — замкнутое ограниченное выпуклое множество, имеющее конечное число угловых точек, то любая точка х Î D может быть представлена в виде выпуклой комбинации угловых точек D*.

* Строгое доказательство данного утверждения см., например, в [14].

Пусть х 1 , х 2 ,…,х m — угловые точки множества D, а х* — точка, в которой целевая функция f достигает максимума.

На основе сформулированного выше утверждения точку х* можно представить в виде выпуклой комбинации угловых точек х 1 , х 2 . x m

Так как х* — точка максимума, то для любого х Î D сх* ≥ сх. Функция f(x) — линейная, поэтому

где x r — угловая точка, удовлетворяющая условию

Из (1.10) видно, что сх* ≤ сх r . В то же время справедливо обратное неравенство: сх* ≥ сх r . Откуда следует, что сх* = сх r , т. е. существует по крайней мере одна угловая точка х r , в которой целевая функция принимает максимальное значение. A

Теорема 1.2. Если целевая функция f принимает максимальное значение в нескольких точках множества D, то она принимает это же значение в любой точке, являющейся их выпуклой комбинацией.

Доказательство.

Пусть максимальное значение функции f достигается в точках х̃ 1 , х̃ 2 . x̃ s , т. е. сх ~ i =f*, iÎ l:s. Рассмотрим произвольную выпуклую комбинацию этих точек

Найдем значение целевой функции в точке х*

Итак, для произвольной выпуклой комбинации х* точек х̃ 1 , х̃ 2 . x ~ s справедливо равенство

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

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

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

1) Изучить теоретические сведения, необходимые для решения задач линейного программирования геометрическим методом.

2) Разобрать алгоритм решения ЗЛП геометрическим методом.

3) Решить поставленные задачи, используя рассмотренный метод решения задач линейного программирования.

1.1 Линейное программирование

Линейное программирование — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Линейное программирование является частным случаем математического программирования. Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования.

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

Математическая формулировка задачи линейного программирования

при условиях при i = 0, 1, 2, . . . , m .

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

Такую задачу называют "основной" или "стандартной" в линейном программировании.

1.2 Формулировка задачи

и система линейных ограничений

где а_ij, b_j и С_j - заданные постоянные величины.

Найти такие неотрицательные значения х₁, х₂, . х_n, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1) минимальное значение.

Общая задача имеет несколько форм записи.

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях А₁х₁ + А₂x₂ + . + А_Nx_N = А_о, X₀ (1.4)

где С = (с₁, с₂, . с_N); Х = (х₁, х₂, . х_N); СХ - скалярное произведение; векторы A₁ = A₂ = . A_N состоят соответственно из коэффициентов при неизвестных и свободных членах.

Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А₀Х₀, где С = (с₁, с₂, . с_N) - матрица-cтрока; А = (а_ij) - матрица системы; Х =(x_ij)- матрица-столбец, А₀ = (а_i) матрица-столбец

Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = С_jх_j при ограничениях

0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х₁, х₂, . х_N), удовлетворяющий условиям (1.2) и (1.3).

0пределение 2. План Х = (х₁, х₂, . х_N) называется опорным, если векторы А (i = 1, 2, . N), входящие в разложение (1.4) с положительными коэффициентами х , являются линейно независимыми.

Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

0пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным.

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

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

1.3 Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования

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

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

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

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

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

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

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

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

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

Линейная комбинация векторов а 1 , а 2 . а m называется выпуклой, если λ_i ≥0, i €1:m и

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

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

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

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

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

1.4 Математические основы решения задачи линейного программирования графическим способом

1.4.1 Математический аппарат

Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = 3.

Наиболее наглядна эта интерпретация для случая n = 2, т.е. для случая двух переменных x₁ и x₂. Пусть нам задана задача линейного программирования в стандартной форме

Возьмём на плоскости декартову систему координат и каждой паре чисел (x₁,x₂)поставим в соответствие точку на этой плоскости.

Обратим прежде всего внимание на ограничения x₁ ≥0 и x₂ ≥ 0. Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида a₁ x₁ + a₂ x₂ ≤ b. Сначала рассмотрим область, соответствующую равенству a₁ x₁ + a₂ x₂ = b. Как Вы, конечно, знаете, это прямая линия. Строить её проще всего по двум точкам.

Пусть b ≠ 0. Если взять x₁ = 0, то получится x₂ = b/a₂. Если взять x₂ = 0, то получится x₁ = b/a₁. Таким образом, на прямой лежат две точки (0, b/a₂) и (b/a₁, 0). Дальше через эти две точки можно по линейке провести прямую линию (рисунок 2).

Если же b=0, то на прямой лежит точка (0,0). Чтобы найти другую точку, можно взять любое отличное от нуля значение x₁ и вычислить соответствующее ему значение x₂.

Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части a₁x₁ + a₂x₂ b. Узнать, в какой полуплоскости, какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).

1.4.2 Геометрическая интерпретация задачи линейного программирования

Рассмотрим задачу ЛП в стандартной форме записи:

х_j ≥ 0, j = 1, 2, …, n.

Рассмотрим эту задачу на плоскости, т.е. при п = 2. Пусть система неравенств (**), (***) совместна (имеет хотя бы одно решение):

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой а_i₁х₁ + а_i₂х₂ ≤ b_i i = 1, m. Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми x₁ = 0; х₂ = 0.. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых составляют решение данной системы. Совокупность этих точек называют многоугольником решений. Это может быть точка, отрезок, луч, замкнутый многоугольник, неограниченная многоугольная область.

Если в системе ограничений (**) - (***) n = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого а_i₁х₁ + а_i₂х₂ + а_i₃х₁ ≤ b_i, а условия неотрицательности — полупространства с граничными плоскостями соответственно x_i = 0 (i = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений.

Пусть в системе (**) - (***) п > 3, тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью а_i₁х₁ + а_i₂х₂ + … + а_inх_n ≤ b_i i = 1, т , а условия неотрицательности — полупространства с граничными гиперплоскостями x_j = 0, j = 1, n.

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

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

1.4.3 Этапы решения графического метода задач линейного программирования

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

Пусть задача линейного программирования задана в двумерном пространстве, т. е. ограничения содержат две переменные.

Если в ЗЛП ограничения заданы в виде неравенств с двумя переменными, она может быть решена графически. Графический метод решения ЗЛП состоит из следующих этапов.

Сначала на координатной плоскости x₁Ox₂ строится допустимая многоугольная область (область допустимых решений, область определения), соответствующая ограничениям:

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

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

2. Неосновной случай  получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 1б. Подобная ситуация, например, получится, если в рассмотренном выше примере убрать ограничение х₁ + х ₂ ≤ 3. Оставшаяся часть будет неограниченным выпуклым многоугольником.

Наконец, возможен случай, когда неравенства (1.6) противоречат друг другу, и допустимая область вообще пуста.

Рассмотрим теорию на конкретном примере:

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

1. Рассмотрим прямую –x₁+x₂ = 1. При x₁ = 0, x₂ = 0, а при x₂= 0, x₁= -1. Таким образом, эта прямая проходит через точки (0,1) и (-1,0). Беря x₁ = x₂ = 0, получим, что -0+0 max.

Рис. 6

Рассмотрим прямую с₁х₁+с₂х₂ = L. Будем увеличивать L. Что будет происходить с нашей прямой?

Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором (с₁,с₂), так как это  вектор нормали к нашей прямой и одновременно вектор градиента функции

А теперь сведем всё вместе. Итак, надо решить задачу

Ограничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L прямая с₁х₁+с₂х₂ = L пересекает допустимую область. Это пересечение дает какие-то значения переменных (х₁,х₂), которые являются планами.

Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 7). В конце концов эта прямая выйдет на границу допустимой области  как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение прямой с₁х₁+с₂х₂ = L с допустимой областью будет пустым. Поэтому то положение прямой с₁х₁+с₂х₂ = L, при котором она вышла на граничную точку допустимой области, и даст решение задачи, а соответствующее значение L и будет оптимальным значением целевой функции.

II. ПРАКТИЧЕСКИЙ РАЗДЕЛ

Задача №1

Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице 1.1..

Система ограничений ЗЛП геометрически представляет собой многоугольник или многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы. Целевая функция f = c₁x₁ + c₂x₂ геометрически изображает семейство параллельных прямых, перпендикулярных вектору n (с₁,с₂).

Теорема. При перемещении прямой целевой функции направлении вектора n значения целевой функции возрастают, в противоположном направлении - убывают.

На этих утверждениях основан графический метод решения ЗЛП.

Алгоритм графического метода решения ЗЛП.

· В системе координат построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений;

· найти полуплоскости решения каждого неравенства системы (обозначить стрелками);

· найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей;

· построить вектор n (с₁,с₂) по коэффициентам целевой функции f = c₁x₁ + c₂x₂;

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

· перемещать прямую целевой функции параллельно самой себе по области решения, достигая max f при движении вектора n и min f при движении в противоположном направлении.

· найти координаты точек max и min по чертежу и вычислить значения функции в этих точках (ответы).

Постановка транспортной задачи.

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

Однородный груз, имеющийся в m пунктах отправления (производства) А₁, А₂, . А_m соответственно в количествах а₁, а₂, . а_mединиц, требуется доставить в каждый из n пунктов назначения (потребления) В₁, В₂, . В_n соответственно в количествах b₁, b₂, . b_n единиц. Стоимость перевозки (тариф) единицы продукта из A_i в B_j известна для всех маршрутов A_iB_j и равна C_ij (i=1,m; j=1,n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозиться и запросы всех пунктов потребления удовлетворяются (закрытая модель), а суммарные транспортные расходы минимальны.

Условия задачи удобно располагать в таблицу, вписывая в клетки количество перевозимого груза из A_i в B_jгруза X_ij > 0, а в маленькие клетки - соответствующие тарифы C_ij:

Математическая модель транспортной задачи.

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

Число r = m + n - 1, равное рангу системы (1), называется рангом транспортной задачи. Если число заполненных клеток (X_ij <>0) в таблице равно r, то план называется невырожденным, а если это число меньше r, то план вырожденный - в этом случае в некоторые клетки вписывается столько нулей (условно заполненные клетки), чтобы общее число заполненных клеток было равно r.

Случай открытой модели легко сводится к закрытой модели путем введения фиктивного потребителя B_n+1 c потребностью b_n+1=Σa_i-Σb_j, либо - фиктивного поставщика А_m+1 c запасом a_m+1=Σb_j-Σa_i ; при этом тарифы фиктивных участников принимаются равными 0.

Способы составления 1-таблицы (опорного плана).

Способ северо-западного угла (диагональный). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью вывозиться груз из А_i, либо полностью удовлетворяется потребность B_j. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы a_i и не удовлетворяются потребности b_j. В заключение проверяют, что найденные компоненты плана X_ij удовлетворяют горизонтальным и вертикальным уравнениям и что выполняется условие невырожденности плана.

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

Метод потенциалов решения транспортной задачи.

Определение: потенциалами решения называются числа _iA_i, _jB_j, удовлетворяющие условию _i+_j=C_ij (*) для всех заполненных клеток (i,j).

Соотношения (*) определяют систему из m+n-1 линейных уравнений с m+n неизвестными, имеющую бесчисленное множество решений; для ее определенности одному неизвестному придают любое число (обычно ₁=0), тогда все остальные неизвестные определяются однозначно.

Критерий оптимальности. Если известны потенциалы решения X₀ транспортной задачи и для всех незаполненных клеток выполняются условия_i+_j C_{i j}, то X₀ является оптимальным планом транспортной задачи.

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

Определение: циклом пересчета таблицы называется последовательность клеток, удовлетворяющая условиям:

· одна клетка пустая, все остальные занятые;

· любые две соседние клетки находятся в одной строке или в одном столбце;

· никакие 3 соседние клетки не могут быть в одной строке или в одном столбце .

Пустой клетке присваивают знак “ + ”, остальным - поочередно знаки “ - ” и “ + ”.

Для перераспределения плана перевозок с помощью цикла перерасчета сначала находят незаполненную клетку (r, s), в которой _r+_sC_rs, и строят соответствующий цикл; затем в минусовых клетках находят число X=minij>.Далее составляют новую таблицу по следующему правилу:

· в плюсовые клетки добавляем X;

· из минусовых клеток отнимаем Х;

· все остальные клетки вне цикла остаются без изменения.

Получим новую таблицу, дающее новое решение X, такое, что f(X₁) f(X₀); оно снова проверяется на оптимальность через конечное число шагов обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

Алгоритм метода потенциалов.

· проверяем тип модели транспортной задачи и в случае открытой модели сводим ее к закрытой;

· находим опорный план перевозок путем составления 1-й таблицы одним из способов - северо-западного угла или наименьшего тарифа;

· проверяем план (таблицу) на удовлетворение системе уравнений и на не вырожденность; в случае вырождения плана добавляем условно заполненные клетки с помощью “ 0 ”;

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

· а) составляем систему уравнений потенциалов по заполненным клеткам;

· б) находим одно из ее решений при ₁=0;

· в) находим суммы_i+_j=C_ij (“косвенные тарифы”) для всех пустых клеток;

· г) сравниваем косвенные тарифы с истинными: если косвенные тарифы не превосходят соответствующих истинных(C_ij C_ij) во всех пустых клетках, то план оптимален (критерий оптимальности). Решение закончено: ответ дается в виде плана перевозок последней таблицы и значения min f.

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

Для перехода к следующей таблице (плану):

· а) выбираем одну из пустых клеток, где косвенный тариф больше истинного (C_ij=_i+_j > C_ij );

· б) составляем цикл пересчета для этой клетки и расставляем знаки “ + ”, “ - ” в вершинах цикла путем их чередования, приписывая пустой клетке “ + ”;

· в) находим число перерасчета по циклу: число X=minij>, где X_ij- числа в заполненных клетках со знаком “ - ”;

· г) составляем новую таблицу, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла

Через конечное число шагов (циклов) обязательно приходим к ответу, ибо транспортная задача всегда имеет решение.

Раздел: Информатика, программирование
Количество знаков с пробелами: 12872
Количество таблиц: 0
Количество изображений: 4

Перейдем к геометрической интерпретации целевой функции. Уравнение при фиксированном значении определяет на плоскости прямую линию. При изменении Z получим семейство параллельных прямых, называемых линиями уровня. Вектор с координатами из коэффициентов при и перпендикулярен к каждой из линий уровня. Вектор показывает направление наибольшего возрастания (убывания) целевой функции. Каждое… Читать ещё >

задачи линейного программирования
геометрическая интерпретация и графическое решение

Геометрическая интерпретация и графическое решение ЗЛП ( реферат , курсовая , диплом , контрольная )

Задача с двумя переменными.

Пусть требуется найти решение, доставляющее:

Начнем с геометрической интерпретации области допустимых решений.

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

Если построить на одном рисунке область допустимых решений, вектор и одну из линий уровня, например, Z=0, то задача сводится к определению в области допустимых решений точки в направлении вектора, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции Z. Это и есть графический способ решения ЗЛП. Если задача разрешима, могут представиться следующие случаи: задача имеет единственное решение (рис. 2, а); задача имеет бесконечное множество — альтернативный оптимум (рис. 2, б); целевая функция не ограничена; область допустимых решений — единственная точка, задача не имеет решения.

Читайте также: