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

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

Задачи линейного программирования можно решить следующими методами:

алгоритмом Флойда;

алгоритм Дейкстры на графах;

графический метод;

метод симплекс-таблиц и др.

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

В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U - массив булевых переменных.

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

На каждом шаге цикла необходимо найти вершину U с минимальным расстоянием и флагом равным нулю. Затем нужно установить в ней флаг в 1 и проверяем все соседние с ней вершины U. Если расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то необходимо уменьшить его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0. Последний случай возможен тогда и только тогда, когда граф G не связан.

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

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

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

Минимальное значение функции определено формулой (1).

(1)

Ограничения представлены формулами (2) и (3).

(2)

(3)

Пусть система (2) при условии (3) совместна. Каждое из неравенств из систем (2) и (3) определяет полуплоскость с граничными прямыми представлено формулой(4):

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

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

Найти точку многоугольника решений, в которой прямая
опорная и функция Z при этом достигает минимума.

Значения
уменьшаются в направлениивектора
, поэтому прямую Z=0 необходимо передвигать параллельно самой себе в направлении вектора N.

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

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

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

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

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

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

Перед составлением симплекс-таблицы задача должна быть преобразована, система ограничений приведена к допустимому базисному виду, c помощью которого из целевой функции должны быть исключены базисные переменные как показано на рисунке 1.

Рисунок 1 – Начальное преобразование системы ограничений

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X1, X2, ..., Xr и что при этом b1, b2,..., br ≥ 0 (соответствующее базисное решение является опорным).

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

Рисунок 2 – Преобразование системы неравенств

Алгоритм перехода к следующей таблице такой:

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

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

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

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

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

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

в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.

столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же.

в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы, как показано на рисунке 3.

Рисунок 3 – Составление нового элемента в симплекс-таблице

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

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

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

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

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

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

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

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

Реализацию графического метода решения ЗЛП рассмотрим на примерах.

Пример 2.2.1. Решить ЗЛП графическим методом:

(2.2.1)

max z =x 1 + 4x 2 (2.2.2)

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

l 1: x 1 + 5x 2 = 5; l 2: x 1 + x 2 = 6; l 3: 7x 1 + x 2 = 7.

l 1 к виду (2.2.3.) разделим обе его части на 5:
. Таким образом, прямаяl 1 отсекает на оси Ох 1 5 единиц, на оси Ох 2 1 единицу. Аналогично имеем для l 2:
иl 3:
.

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

Таким образом, первая и вторая искомые полуплоскости расположены в противоположную сторону от начала координат (0 – 5·0– 5; 7·0 + 07), а вторая – в сторону начала координат (0 + 06). Область допустимых решений на рисунке 2.2.1 заштрихована.

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

Для нахождения оптимального плана, который будет находиться в вершине многоугольника решений, нужно построить вектор направлений
=(с 1 ,с 2), который указывает направление наибольшего возрастания целевой функцииz =с 1 х 1 +с 2 х 2 .

В данной задаче вектор направлений
= (1, 4): он начинается в точкеО (0,0) и заканчивается в точкеN (1, 4).

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

Таким образом, точкой максимума целевой функции z является точкаА пересечения прямыхl 2 иl 3 .

Для вычисления оптимального значения целевой функции z найдем координаты точки А. Поскольку точка А – это точка пересечения прямых l 2 и l 3 , то ее координаты удовлетворяют системе уравнений, составленной из уравнений соответствующих граничных прямых:

Таким образом, точка А имеет координаты x 1 =1/6, x 2 = 35/6.

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

Подставив координаты точки А в целевую функцию (2.4), получим

max z = 1/6 + 4·(35/6) = 47/2.

Пример 2.2.2. Построить на плоскости область допустимых решений системы линейных неравенств (2.2.4) и найти наибольшее и наименьшее значения целевой функции (2.2.5):

(2.2.4)

z = –2x 1 –x 2 (2.2.5)

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

l 1: 4x 1 – x 2 = 0; l 2: x 1 + 3x 2 = 6; l 3: x 1 – 3x 2 = 6; l 4: x 2 = 1.

Прямая l 1 проходит через точку с координатами (0;0). Для ее построения выразим x 2 через x 1: x 2 = 4x 1 . Найдем еще одну точку, через которую проходит прямая l 1 , например (1;4). Через точку с координатами (0;0) и точку с координатами (1;4) проведем прямую l 1 .

Для приведения уравнения прямой l 2 к виду в отрезках на осях (2.2.3) разделим обе его части на 6:
. Таким образом, прямаяl 2 отсекает на оси Ох 1 6 единиц, на оси Ох 2 - 2 единицы. Аналогично имеем для l 3:
и Прямаяl 4 параллельна оси Ох 1 и проходит через точку с координатами (0;1) .

Для определения полуплоскостей, которые отвечают ограничениям системы (2.2.4) в ограничения нужно подставить координаты какой-либо точки, не лежащей на граничной прямой. В силу ограничений х 1 0, х 2 0, область допустимых решений ЗЛП лежит в первой четверти координатной плоскости.

О
бласть допустимых решений на рисунке 2.2.2 заштрихована.

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

Построим вектор направлений
= (–2,–1). Далее строим линию уровня, перпендикулярно к вектору.

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

Для вычисления оптимального значения целевой функции z найдем координаты точкиА . Поскольку точкаА – это точка пересечения прямыхl 1 иl 2 , то ее координаты удовлетворяют системе уравнений, составленной из уравнений соответствующих граничных прямых:

Таким образом, точка А имеет координаты x 1 =6/13, x 2 = 24/13.

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

max z = – 2·(6/13) – (24/13) = – 36/13.

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

В результате решения ЗЛП возможны следующие случаи:

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

Целевая функция достигает оптимальное значение в любой точке ребра многоугольника решений (ЗЛП имеет альтернативные опорные планы с одинаковыми значениями z);

ЗЛП не имеет оптимальных планов;

ЗЛП имеет оптимальный план в случае неограниченной области допустимых решений.

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

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

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

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

можно представить в виде системы двух неравенств

ЦФ при фиксированном значении определяет на плоскости прямую линию. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

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

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

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

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

Рисунок 1 Геометрическая интерпретация ограничений и ЦФ задачи

Рассмотрим методику решения задач ЛП графическим методом.

• 1) в ограничениях задачи (1) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые;
• 2) найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

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

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

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

• 3) определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений;
• 4) если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений;
• 5) построить вектор, который начинается в точке (0;0) и заканчивается в точке. Если целевая прямая и вектор построены верно, то они будут перпендикулярны;
• 6) при поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора, при поиске минимума ЦФ - против направления вектора. Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум);
• 7) определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится.

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

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

Рисунок 2 Переход от одной вершины к другой

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

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.

Алгоритм решения ЗЛП симплексным методом.

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

Рассмотрим шаги симлекс-метода.

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

Таблица 1

Пример симплекс-таблицы

• 3) на третьем шаге пересчитываем всю симплекс-таблицу по специальным формулам;
• 4) если после перерасчета в столбце свободных членов остались отрицательные элементы, то переходим к первому шагу, если таких нет, то к пятому;
• 5) если Вы дошли до пятого шага, значит нашли решение, которое допустимо. Однако, это не значит, что оно оптимально. Оптимальным оно будет только в том случае, если положительны все элементы в F-строке. Если же это не так, то необходимо улучшить решение, для чего находим для следующего перерасчета ведущие строку и столбец по следующему алгоритму. Первоначально, находим минимальное отрицательное число в строке F, исключая значение функции. Столбец с этим числом и будем ведущим. Для того, что бы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они положительны. Минимальное отношение позволит определить ведущую строку. Вновь пересчитываем таблицу по формулам, т.е. переходим к шагу 3;
• 6) если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена сверху и F max ->?. Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

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

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

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

Таблица 1.

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

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

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

Краткая теория

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

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

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

Пример решения задачи

Условие задачи

Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить кг сырья первого типа, кг сырья второго типа, кг сырья третьего типа. На изготовление единицы Изделия 2 требуется затратить кг первого типа, сырья второго типа, сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве кг, кг, кг соответственно. Рыночная цена единицы Изделия 1 составляет тыс руб., а единицы Изделия 2 - тыс. руб.

Требуется:

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

Решение задачи

Построение модели

Через и обозначим количество выпускаемых изделий 1-го и 2-го типа.

Тогда ограничения на ресурсы:

Кроме того, по смыслу задачи

Целевая функция экономико-математической модели, выражающая получаемую от реализации выручку:

Получаем следующую экономико-математическую модель:

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

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

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

Найдем точки, через которые проходят прямые:

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

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

Области решений соответствующего 1-го неравенства соответствует левая полуплоскость

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

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

Области решений соответствующего 2-го неравенства соответствует левая полуплоскость

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

Нахождение решения задачи ЛП

Строим вектор , координаты которого пропорциональны коэффициентам целевой функции. Здесь - коэффициент пропорциональности.

Перпендикулярно к построенному вектору проводим линию уровня .

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

Ответ

Таким образом необходимо выпускать 56 изделий 1-го вида и 64 изделия 2-го вида. При этом выручка от реализации изделий будет максимальна и составит 5104 ден.ед.

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

На цену сильно влияет срочность решения (от суток до нескольких часов). Онлайн-помощь на экзамене/зачете осуществляется по предварительной записи.

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