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

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

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

Общая задача линейного программирования.

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

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

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

Математическое программирование возникло в 30е годы ХХ века. Венгерский математик Б.Эгервари в 1931 году решил задачу, называемую проблемой выбора. Американский ученый Г.У. Кун обобщил этот метод, после чего он стал называться «венгерским методом». В 1939 году российский ученый Л.В. Канторович разработал метод разрешающих множителей решения задач линейного программирования. Большой вклад в развитие математического программирования внесли американские ученые. В 1947 году американский ученый Дж.Данцит описал один из основных методов решения задач линейного программирования, получивший названия «симплексный».

Метод называется симплексным, так как области допустимых решений задач, которые рассматривались на начальном этапе развития метода, имели простейший (simple) вид (n=2, n=3).

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

1. выбор переменных задачи;

2. составление системы ограничений;

3. выбор целевой функции.

Переменными задачи называются величины х1, х2, . хn, которые полностью характеризуют экономический процесс.

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

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

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

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор Х=(х1, х2, . хn), удовлетворяющий системе ограничений и условиям неотрицательности.

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

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

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

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

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

Обратим прежде всего внимание на ограничения х1 ≥0, и х2 ≥0. Они из всей плоскости вырезают лишь её первую четверть (рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида а1 х12 х2≤b. Сначала рассмотрим область, соответствующую равенству а1 х12 х2=b. Это прямая линия. Строить её проще всего по двум точкам.

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

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

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

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

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

Читать еще:  Принципы модульного программирования

Рассмотрим случай двух переменных:

(5)

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

Каждое из ограничений (6), (7) задаёт на плоскости x1Ox2 некоторую полуплоскость. Полуплоскость – выпуклое множество. Напомним, что выпуклым называют множество, которое вместе с любыми своими точками x1 и x2 содержит и все точки отрезка [ x1; x2]. Пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений (ОДР) задачи есть выпуклое множество.

Возможны ситуации, когда область допустимых решений ЗЛП:

— неограниченная выпуклая многоугольная область;

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

Пусть ОДР задачи ЛП – непустое множество.

Выберем произвольное значение целевой функции , получим . Это уравнение прямой линии. В точках прямой целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции. Найдем частные производные целевой функции по x1 и x2: .

Частная производная функции показывает скорость её возрастания вдоль данной оси. с1 и с2 – скорости возрастания соответственно вдоль осей Ox1 и Ox2. Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции. Вектор указывает направление наискорейшего убывания целевой функции Его называют антиградиентом.

Вектор перпендикулярен к прямой семейства .

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

1. С учетом системы ограничений строится область допустимых решений.

2. Строится вектор .

3. Проводится произвольная линия, перпендикулярная к вектору .

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

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

5. Определяется оптимальный план и экстремальное значение целевой функции .

Возможны следующие случаи:

— оптимальный план единственный;

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

— целевая функция неограниченна;

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

— задача не имеет решения: ОДР – пустое множество, т.е. система ограничений задачи несовместна.

Пример. Пусть предприятие изготавливает изделия двух видов А и В. Для производства изделий оно располагает сырьевыми ресурсами 3-х видов С, D и E в объёмах 600, 480 и 240 единиц соответственно. Нормы расхода ресурсов на единицу продукции каждого вида известны и даны в таблице 1. Прибыль от реализации изделия А составляет 40 млн. руб., а изделия В- 50 млн. руб. Требуется найти объёмы производства изделий, обеспечивающие максимальную прибыль.

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

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

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

Если провести прямые, соответствующие условиям [(1)-(3)] задачи, получим область допустимых решений (ОДР).

Неравенства и целевую функцию задачи с двумя переменными можно изобразить в виде прямых линий в декартовой системе координат с осями x1, x2. Для этого заменим неравенства (1-3) уравнениями. Определим для каждого уравнения координаты двух точек, через которые проходит прямая. Для первого уравнения найдем две точки, через которые проведем прямую: .

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

3. Для третьего уравнения определим координаты двух точек ; . через которые проведем прямую.

Заштрихуем каждую прямую со стороны области допустимых значений.

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

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

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

при Z=10

при

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

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

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

Последний случай мог бы реализоваться, если бы, например, отношение коэффициентов целевой функции C1 и C2 при неизвестных X1 и X2 в уравнении целевой функции было таким же, как и у коэффициентов при неизвестных во втором ограничении.

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

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

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

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

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

Алгоритм – точное описание последовательности действий при решении задачи. Для определения первого (опорного) решения необходимо перейти к каноническому представлению задачи, в котором все ограничения имеют форму уравнений (т. е. относятся к типу “=”).

Лекция 4: Метод полного исключения. Табличный симплекс – метод. Геометрическая интерпретация задач линейного программирования

2. Табличный симплекс — метод

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

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

Применим одну итерацию метода полного исключения к расширенной матрице ограничений Ap=[A1, . An, e1, . em, A] .

Пусть aij — направляющий элемент преобразования на данной итерации. Тогда в результате преобразований в соответствии с (1.10) получим новые значения свободных членов:

Исследуем выражения (2.1) и выясним условия, при которых 0″ style=»display: inline; «> для всех l , то есть новое базисное решение будет также допустимым.

По предположению 0; l=1. m, a_^ <(k)>> 0″ style=»display: inline; «>, тогда

Если , тогда 0″ style=»display: inline; «>, поскольку 0, ; a_^ <(k)>> 0″ style=»display: inline; «>.

Если 0″ style=»display: inline; «>, то

Преобразование Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:

a) направляющий столбец j выбирают из условия, что в нем имеется хотя бы один положительный элемент;

б) направляющую строку i выбирают так, чтобы отношение было минимально при условии, что aij>0 .

При таком преобразовании в базис вводится вектор Aj и выводится вектор Аi . Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.

Для этого используют так называемые оценки векторов :

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

Для решения задачи симплекс-методом на каждой итерации заполняют симплекс-таблицу 2.1.

Последняя строка таблицы — индексная — служит для определения направляющего столбца. Ее элементы определяют по формуле (2.3). Очевидно, для всех базисных векторов i> i=1. m оценки .

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

В столбце Bx записываем базисные переменные i> i= 1, . m . Их значения определяются столбиком свободных членов ai0 , то есть

Направляющие строка Ai и столбец Aj указываются стрелками. Если в качестве направляющего элемента выбран aij , то переход от данной симплекс-таблицы к следующей определяется соотношениями (1.8) — (1.10).

Итак, алгоритм решения задачи ЛП табличным симплекс-методом состоит из этапов.

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

2. В качестве направляющего столбца выбирают Aj , для которого

3. Направляющая строка Aі выбирают из условия

4. Делают один шаг (итерацию) метода полного исключения Гаусса с направляющим элементом aij , для чего используют соотношения (1.8) — (1.10). В частности, элементы индексной строки новой таблицы вычисляют в соответствии с формулой

5. Если все , то новое базисное решение — оптимально. В противном случае переходят к этапу 2 и выполняют очередную итерацию.

6. Второй, третий и четвертый этапы повторяют до тех пор, пока одна из итераций не закончится одним из двух исходов:

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

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

Назовем некоторые особенности применения табличного симплекс-метода .

Если в качестве начального базиса выбирают базис из свободных переменных, для которых ci=0 , то оценки для всех небазисных переменных равны , а соответствующее значение целевой функции

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

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

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

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

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

Исследование операций

Семинар

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

Определение выпуклой области.Пусть на плоскости xOy заданы две точки: А1 (x (1) ; y (1) ) и А2 (x (2) ; y (2) ), определяющие прямолинейный направленный отрезок (рис.1.2). Найдем координаты произвольной внутренней точки А (x; y) данного отрезка через координаты его начала и конца.

(2.43)

Учитывая, что в (2.43) координаты точки А являются суммами одноименных координат точек А1 и А2, умноженными соответственно на числа l1 и l2, окончательно имеем:

Точка А, для которой выполняются условия (2.44) и (2.45), называется выпуклой линейной комбинацией точек А1 и А2. Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и их произвольную выпуклую линейную комбинацию. Геометрический смысл этого определения состоит в том, что множеству вместе с его двумя произвольными точками полностью принадлежит и прямолинейный отрезок, их соединяющий. Точка множества называется граничной, если любой шар сколь угодно малого радиуса с центром в этой точке содержит как точки, принадлежащие множеству, так и точки, не принадлежащие ему. Граничные точки множества образуют его границу. Замкнутым называется множество, содержащее все свои граничные точки. Замкнутое множество называется ограниченным, если существует шар радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество; в противном случае множество называется неограниченным. Пересечением двух (или нескольких) множеств называется множество, представляющее общую часть данных множеств. Точка A выпуклого множества называется угловой, если она не может быть представлена в виде выпуклой линейной комбинации каких-нибудь двух различных точек данного множества. Выпуклым многоугольником называется выпуклое замкнутое ограниченное множество на плоскости, имеющее конечное число угловых точек. Угловые точки многоугольника называются его вершинами, а отрезки, соединяющие две вершины и образующие его границу, — сторонами многоугольника.

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

Т е о р е м а 2.Замкнутый, ограниченный, выпуклый многогранник является выпуклой линейной комбинайией своих угловых точек.

Доказательство. Рассмотрим многоугольник, имеющий n вершин.

1) Докажем, что любая точка треугольника удовлетворяет теореме. В треугольнике A1А2А3 (рис.2.3) возьмем произвольную точку А4 и через нее проведем отрезок А1А4.

Так как точка А принадлежит отрезку А1А4, то она — выпуклая линейная комбинация его концов, т. е.

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

Подставляя (2.47) в (2.46) получаем

2) В выпуклом многоугольнике, имеющем n вершин (n > 3), добавляя к правой части соотношения (2.48) остальные n ‑ 3 вершины, умноженные на нуль, окончательно получим

lI ³ 0 (i = 1, 2, . n), ,

т. е. точка А — выпуклая линейная комбинация угловых точек многоугольника.

Лемма 1. Пересечение любого числа выпуклых множеств есть множество выпуклое (если оно не пусто).

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

Пусть дана задача

(2.50)

Совокупность чисел х1, х2, . хn, удовлетворяющих ограничениям называется решением. Если система неравенств (2.50) при условии (2.51) имеет хотя бы одно решение, она называется совместной, в противном случае несовместной. Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений задает на плоскости х1Ох2 некоторую полуплоскость с граничной прямой аi1x1 + аi2x2 = bi (i = 1, 2, . m). Полуплоскость — выпуклое множество. Но по лемме 1 пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (2.49)—(2.51) есть выпуклое множество.

Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х1 = 0, х2 = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек (решений) назовем многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

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

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — непустое множество. Например, многоугольник А1А2А3А4А5А6 (рис. 2.4). Выберем произвольное значение целевой функции Z = Z. Получим C1x1 + C2x2 = Z. Это уравнение прямой линии. В точках прямой NM целевая функция сохраняет одно и то же постоянное значение Z. Считая в равенстве (2.49) Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

IT Новости из мира ПК
Добавить комментарий