Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

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

, , .

Геометрическая интерпретация решения:

.

Нормальное уравнение прямой: ,

,

,

.

Рис. 3.1. Геометрическая интерпретация решения экстремальной задачи

То есть наискорейшее возрастание функции F будет в направлении вектора . Координаты точки В удовлетворяют уравнению:

.

Можно показать, что если задача линейного программирования имеет решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений. Поэтому для решения задачи линейного программирования необходимо перебрать конечное число базисных решений, выбрать среди них то, на котором целевая функция принимает экстремальное значение. Геометрически это соответствует перебору всех угловых (крайних) точек многогранника. Если оптимальное решение существует, то такой перебор приведет к нахождению оптимального решения. Однако такой прямой перебор связан с очень большим объемом вычислений. Число перебираемых допустимых базисных решений можно сократить, если производить перебор не произвольно, а добиваясь того, чтобы каждое последующее решение было бы не хуже предыдущего. Такой подход, хотя и не исключает теоретической возможности перебора всех угловых точек, на практике позволяет существенно сократить число шагов при отыскании экстремума. Поясним это на графическом примере (см. рис. 3.2).

Пусть область допустимых решений изображается многоугольником ABCDEFGH. Пусть угловая точка B соответствует исходному допустимому базисному решению. При произвольном переборе всех вершин мы могли бы исследовать все семь вершин многогранника. В то же время видно, что после точки B выгоднее перейти к точке C , а затем к точке D, которая и будет оптимальной, т.е. вместо семи точек перебрали только три.

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

Рис.3.2. Область допустимых решений

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

Симплексный метод состоит из трех основных элементов:

1) определения какого-либо первоначального допустимого базисного решения;

2) правила перехода к лучшему решению;

3) проверки оптимальности допустимого решения.

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

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

4.1. Формы задач линейного программирования.

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

4.1. Формы задач линейного программирования и их эквивалентные преобразования[15]

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

1. Стандартная задача линейного программирования

, или

;

. .

Стандартная задача линейного программирования – это задача, в которой система функциональных и прямых ограничений состоит из одних неравенств, переменные являются неотрицательными, а целевая функция может стремиться как к максимуму, так и к минимуму. Причем, в стандартной ЗЛП на максимум все функциональные ограничения имеют форму «меньше или равно». В стандартной ЗЛП на минимум все ограничения имеют форму «больше или равно».

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

2. Каноническая задача линейного программирования

;

.

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

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

3. Общая задача линейного программирования. Необходимо максимизировать (или минимизировать) линейную функцию от n переменных x1, ¼, xn вида

,

,

.

Стандартная задача получается как частный случай общей при k = m, l = n; каноническая задача получается как частный случай общей при k = 0, l = n.

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

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

— переход от задачи на минимум к задаче на максимум и обратно;

— переход от ограничения в виде неравенства «больше или равно» к ограничению в виде неравенства «меньше или равно»;

— переход от ограничения в виде неравенства к ограничению в виде равенства;

— переход от переменных любого знака к неотрицательным переменным.

Переход от задачи на минимум функции g(`X) к задаче на максимум заключается в рассмотрении задачи на максимум функции — g(`X):

Читать еще:  Важнейшие аспекты информационной безопасности

.

И наоборот переход от задачи на максимум функции f(`X) к задаче на минимум заключается в рассмотрении задачи на минимум функции — f(`X):

.

Если система ограничений какой-либо задачи включает неравенства разного вида, то необходимо привести исходную ЗЛП к стандартной форме записи, т.е. для ЗЛП на максимум привести все неравенства функциональных ограничений к виду «меньше или равно», а для ЗЛП на минимум – к виду «больше или равно». Для этого используются следующие эквивалентные преобразования:

В задаче на максимум все члены слева и справа от неравенства умножают на (-1), а знак неравенства меняют на противоположный:

исходные неравенства: ;

получаемые в результате преобразования неравенства: .

Аналогичным образом поступают и в задаче на минимум:

исходные неравенства: ;

получаемые в результате преобразования неравенства: .

Для решения ЗЛП в стандартной форме записи необходимо перейти к эквивалентной ЗЛП в канонической форме записи. Переход от неканонической модели (хотя бы одно ограничение является неравенством) к канонической осуществляется введением в каждое неравенство балансовой переменной xn+k. При знаке неравенства £ балансовая переменная вводится в неравенство со знаком плюс, т.к. левая часть неравенства меньше правой. Если знак неравенства ³, то балансовая переменная вводится в неравенство со знаком минус, т.к. левая часть неравенства больше правой. При этом для всех балансовых переменных вводится условие неотрицательности. В целевую функцию балансовые переменные не вводятся.

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

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

Если на переменную xj общей задачи не накладывается ограничение неотрицательности, то для того, чтобы общую задачу свести к стандартной, необходимо ввести новые переменные и и положить . Таким образом неотрицательное значение – 5 можно заменить двумя положительными значениями 10 и 15: – 5 = 10 – 15.

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

Дата добавления: 2014-12-03 ; просмотров: 339 ; Нарушение авторских прав

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

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

(1.8)

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

Система ограничений представляет выпуклое множество, а в рассматриваемом двухмерном случае — выпуклый многоугольник ограничений (рис.1.2).

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

Многоугольник ограничений может быть не замкнут (рис.1.4). В этом случае целевая функция не ограничена.

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

Рис.1.1. Геометрический смысл ограничения

Рис.1.2. Геометрическая интерпретация системы ограничений

Для выяснения геометрического смысла целевой функции придадим переменной Z, различные числовые значения (Z=0, Z=1, Z=2, . Z=D).Этим числовым значениям Z соответствует последовательность уравнений и система параллельных прямых в пространстве (рис.1.5).

(1.9)

Рис.1.3. Несовместность системы ограничений

Рис.1.4. Неограниченность целевой функции

Первая прямая (Z=0) проходит через начало координат перпендикулярно (ортогонально) направляющему вектору С=(c1c2), последующие прямые параллельны первой и отстоят от нее в направлении вектора С на величину 1, 2, . D. В целом переменная Z определяет отклонение точек, лежащих на прямой Z=c1x1+c2x2 от прямой c1x1+c2x2=0, проходящей через начало координат. Для того чтобы определить отклонение любой точки от прямой Z=0, достаточно подставить координаты этой точки в уравнение целевой функции.

В n-мерном пространстве целевой функции, приравненной к нулю (Z= c1x1+c2x2+…+cjxj+…+cnxn=0), геометрически соответствует (n-1)-мерная гиперплоскость, проходящая через начало координат. Так как линейная форма Z достигает своего экстремального значения в крайней точке (вершине) многогранника ограничений, то геометрически задача линейного программирования заключается в отыскании вершины многогранника допустимых решений, имеющей максимальное уклонение от гиперплоскости, выраженной целевой функцией, приравненной к нулю (рис.1.6).

Рис.1.5.Геометрическая интерпретация целевой функции

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

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

Для графического решения задачи линейного программирования необходимо:

1. в принятой системе координат построить уравнения всех ограничений, совокупность которых даст многогранник ограничений;

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

Читать еще:  Как включить игру в безопасном режиме

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

4. в соответствие с целью ЗЛП и направлением роста целевой функции, найти точку касания этой прямой (плоскости) с многоугольником (многогранником) ограничений — вершину многоугольника, имеющую максимальное отклонение от прямой (плоскости), проходящей через начало координат.

Рис.1.6. Геометрический смысл оптимального решения задачи линейного программирования

Графический (геометрический) метод решения задач ЛП

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

.

Решение:

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

, воз-можно ее решение геометрическим методом.

1 этап: построение прямых, ограничивающих область допустимых решений ( ОДР).

Рассмотрим систему ограничений задачи линейного програм-мирования (для удобства пронумеруем неравенства):

Рассмотрим первое ограничение, заменим знак неравенства знаком равенства и выразим переменную х2 через х1:

.

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

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

2 этап: определение решения каждого из нера-венств системы ограничений.

Определим полуплоскости – решения каждого из неравенств.

Рассмотрим первое неравенство системы ограничений задачи. Возьмем какую-либо точку (контрольную точку), не принадлежащую соответствующей данному неравенству прямой, например, точку (0; 0). Подставим ее в рассматриваемое неравенство:

.

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

Аналогично определяем решения других неравенств и соответственно помечаем их графике. В результате график примет следующий вид:

3 этап: определение ОДР задачи линейного про- граммирования.

Найденные полуплоскости (решения каждого из неравенств системы ограничений) при пересечении образуют многоугольник ABCDEO, который и является ОДР рассматриваемой задачи.

Рис. 1. Область допустимых решений задачи

4 этап: построение вектора-градиента.
Вектор-градиент показывает направление максимизации целевой функции . Определим его координаты: координаты начальной его точки (точки приложения) – (0; 0), координаты второй точки:

Построим данный вектор на графике (рис. 2).

5 этап: построение прямой целевой функ-ции.

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

.

Зададим ей какое-либо значение, к примеру, . Выразим переменную х2 через х1:

.

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

Построим прямую соответствующую целевой функции (рис. 2).

Рис. 2. Построение целевой функции F(X) и вектора-градиента С

6 этап: определение максимума целевой функ-ции.

Перемещая прямую F(X) параллельно са-мой себе по направлению вектора-градиента, определяем крайнюю точку (точки) ОДР. Согласно графику (рис. 3), такой точкой является точка С ­– точка пересечения прямых I и II.

Рис. 3. Определение точки максимума целевой функции F(X)

Определим координаты точки С, с этой целью, решим сле-дующую систему линейных уравнений:

Подставим найденные координаты в целевую функцию и найдем ее оптимальное (максимальное) значение:

Ответ: при заданных ограничениях макси-мальное значение целевой функции F(Х)=24, которое достигается в точке С, координаты которой х1=6, х2=4.

Пример 6.2. Решить задачу линейного про- граммирования геометрическим методом:

Решение:

Этапы 1-3 аналогичны соответствующим этапам предыдущей задачи.
4 этап: построение вектора-градиента.
Построение вектора-градиента осуществляется аналогично, как и в предыдущей задаче. Построим данный вектор на графике (рис. 4). Отметим также на данном графике стрелкой направление, обратное вектору-градиенту, – направление минимизации целевой функцииF (X).

5 этап: построение прямой целевой функ-ции.

Построение прямой целевой функции F(X) осуществляется аналогично, как и в предыдущей задаче (результат построения приведен на рис. 4).

Рис. 4. Построение целевой функции F(x) и вектора-градиента С

6 этап: определение оптимума целевой функ-ции.

Перемещая прямую F(x) параллельно са-мой себе в направлении, обратном вектору-градиенту, опреде-ляем крайнюю точку (точки) ОДР. Согласно графику (рис. 5), та- кой точкой является точка О с координатами (0; 0).

Рис. 5. Определение точки минимума целевой функции

Подставляя координаты точки минимума в целевую функ-цию, определяем ее оптимальное (минимальное) значение, которое равно 0.
Ответ: при заданных ограничениях минимальное значение целевой функции F(Х)=0, которое достигается в точке О (0; 0).

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

Решение:

Рассматриваемая задача линейного программирования задана в канонической форме, выделим в качестве базисных переменные x 1 и x2.

Составим расширенную матрицу и выделим с помощью метода Жордана- Гаусса базисные переменныеx1 и x 2.

Умножим (поэлементно) первую строку на –3 и сложим со вто-рой:
.

Умножим вторую строку на :

.

Сложим вторую с первой строкой:

.

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

Выразим базисные переменные через свободные:

Выразим целевую функцию также через свободные перемен-ные, для этого подставим полученные значения базисных переменных в целевую функцию:

.

Запишем полученную задачу линейного программирования:

Так как переменные x1 и x2 неотрицательные, то полученную систему ограничений можно записать в следующем виде:

Читать еще:  Язык программирования паскаль кратко

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

Данная задача имеет два проектных параметра, следовательно, возможно ее решение геометрическим мето-дом.

1 этап: построение прямых, ограничивающих область допустимых решений ( ОДР).

Рассмотрим систему ограничений задачи линейного програм-мирования (для удобства пронумеруем неравенства):

Построим прямые, соответствующие каждому неравенству (рис. 6). Прямые пронумеруем согласно принятой ранее схе-ме.

2 этап: определение решения каждого из нера-венств системы ограничений.

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

3 этап: определение ОДР задачи линейного про- граммирования.

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

Рис. 6. Фрагмент MathCAD-документа:

построение области допустимых решений задачи

Ответ: рассматриваемая задача линейного программирования не имеет решения в силу несовместности системы ограничений.

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

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

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

Добро пожаловать на наш сайт!

ПОЗНАНИЕ ПРОДОЛЖАЕТСЯ .

15.04.2019 20:41
дата обновления страницы

Вещество и энергия. Числа и фигуры

Дата создания сайта: 08 / 12 /2012
Дата обновления главной страницы: 15.04.2019 20:41

Математика помогает планированию

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

Требуется составить такой план производства, чтобы доход от реализации шкафов и столов был наибольшим.
Замечание. На изготовление столов и шкафов идут и другие материалы: клей, лак, шурупы, замки, ручки и др. Для упрощения будем считать, что этих материалов достаточно для любого варианта плана.
Предположим, что мастерская сделает х шкафов и у столов, для этого потребуется Зх + у толстых досок. А так как в наличии имеется 360 таких досок, то должно выполняться неравенство Зх + у 360. Ведь мастерская может получить наибольший доход и тогда, когда доски не будут израсходованы полностью.
Рассуждая аналогично, получим следующие неравенства:

При этих условиях доход F, который получит мастерская, составит: F = l 0 X + 6Y (руб.). Таким образом, задачу можно сформулировать так.
Дана система четырех неравенств первой степени (линейных неравенств):

которую называют линейной формой. Требуется среди неотрицательных (из смысла хну ясно, что х > =0, г/ >= 0) решений системы (1) выбрать такое, при котором форма (2) принимает наибольшее значение.

Существует несколько способов решения поставленной задачи. Самый простой из них — геометрический. Но прежде чем приступить к ее решению, выясним, какая геометрическая картина соответствует системе неравенств.
Начнем с простейших примеров. Пусть дано неравенство у > 2. Выберем прямоугольную систему координат хОу; очевидно, что этому неравенству будут удовлетворять все точки плоскости, расположенные выше прямой у — 2 (рис. 1). На рисунке 2 заштрихована часть плоскости, точки которой удовлетворяют неравенству х n ,
где В — число вершин, а п — размерность пространства. При n = 2 (квадрат) В = 4; при n = 3 (обычный трехмерный куб) В = 8; а, например, при n = 10 (десятимерный куб) В = 1024; при n = 76 (как в случае транспортной задачи о перевозке груза из 5 пунктов отправления в 20 пунктов назначения) В выражается числом из 23 цифр.
Отсюда видно, что если решать задачу таким методом, то в некоторых случаях с ней не справится даже электронная счетная машина.
Чтобы упростить решение задач линейного программирования, чаще всего стремятся сделать так, чтобы оптимальное решение совпало с началом координат, где все свободные неизвестные равны нулю.

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

Размещение фотографий и цитирование статей с нашего сайта на других ресурсах разрешается при условии указания ссылки на первоисточник и фотографии.

Ссылка на основную публикацию
Adblock
detector