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

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

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

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

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

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

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

В простейшей реализации для хранения чисел 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 в ОАО «НефАЗ».На покрасочном конвейере, на котором окрашиваются детали. Необходимо покрасить оптимальное количество деталей за одну рабочую смену, чтобы прибыль была максимальной.

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

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

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

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

Цех изготавливает изделия А и Б. Расход сырья, его запас и прибыль от реализации каждого изделия указаны в таблице.

Вид сырья

Расход на изделие

Запас

А

Б

48

12

600

24

21

840

15

27

1350

Прибыль

12

18

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

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

Экономико-математическая модель задачи

Через и обозначим количество выпускаемой продукции вида А и Б соответственно.

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

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

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

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

Построение чертежа

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

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

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

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

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

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

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

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

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

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

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

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

Нахождение оптимального плана

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

Таким образом, необходимо выпускать 40 ед. изделия Б. Изделие а выпускать невыгодно. При этом прибыль будет максимальной и составит 720 д.е.

Цель работы

1. Изучить понятие математической модели.

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

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

4. Научиться приведению задач линейного программирования к стандартной форме.

Теоретическое введение

Понятие математической модели. Математическая модель в задачах линейного программирования (ЛП)

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

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

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

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

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

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

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

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

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

Общая задача математического программирования формулируется следующим образом:

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

Функция (1.1) называется целевой функцией, а ограничения (1.2) – системой ограничений задачи.

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

Обратите внимание на полученный результат. Целевая функция является линейной функцией переменных х 1 , х 2 , …х n ; сами ограничения на значения переменных х 1 , х 2 , …х n имеют вид линейных неравенств. Все это и определило название этого класса задач – задачи линейного программирования .

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

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

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

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

Методика выполнения работы

Примеры задач ЛП

Пример 1.1. Предприятие химической промышленности выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты – 25 денежных единиц (ден. ед.)., выпуск одной тонны серной кислоты – 40 ден. ед. Для выполнения государственного заказа необходимо выпустить не менее 200 т соляной и не менее 100 т серной кислоты. Кроме того, необходимо учитывать, что выпуск кислот связан с образованием опасных отходов. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов, при выпуске одной тонны серной кислоты – 1,2 т опасных отходов. Общее количество опасных отходов не должно превышать 600 т, так как превышение этого ограничения приведет к выплате предприятием крупного штрафа.

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

Составим математическую модель задачи . Для этого введем переменные. Обозначим через x 1 количество выпускаемой соляной кислоты (в тоннах), через x 2 – количество серной кислоты.

Составим ограничения, связанные с необходимостью выполнения государственного заказа. Предприятию необходимо выпустить не менее 200 т соляной кислоты. Это ограничение можно записать следующим образом: x 1 200. Аналогично составим ограничение, устанавливающее, что предприятие должно выпустить не менее 100 т серной кислоты: x 2 100.

Составим ограничение на опасные отходы. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов; значит, общее количество опасных отходов при выпуске соляной кислоты составит 0,5x 1 т. При выпуске серной кислоты образуется 1,2x 2 т опасных отходов. Таким образом, общее количество опасных отходов составит 0,5x 1 +1,2x 2 т. Эта величина не должна превышать 600 т. Поэтому можно записать следующее ограничение: 0,5x 1 +1,2x 2 600 .

Кроме того, переменные по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество выпускаемых кислот. Поэтому необходимо учитывать ограничения неотрицательности: x 1 0; x 2 0.

В данной задаче требуется определить выпуск кислот, при котором прибыль будет максимальной. Прибыль от выпуска одной тонны соляной кислоты составляет 25 ден. ед.; значит прибыль от выпуска соляной кислоты составит 25x 1 ден. ед. Прибыль от выпуска серной кислоты составит 40x 2 ден. ед. Таким образом, общая прибыль от выпуска кислот составит 25x 1 +40x 2 ден. ед. Требуется найти такие значения переменных x 1 и x 2 , при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:

Е=25x 1 +40x 2 → max.

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

0,5x 1 +1,2x 2 600

Е=25x 1 +40x 2 → max.

В этой задаче имеется два ограничения «больше или равно» и одно ограничение «меньше или равно». Целевая функция подлежит максимизации.

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

Математическая модель такой задачи имеет следующий вид:

25x 1 +40x 2 20000

Е= 0,5x 1 +1,2x 2 → min.

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

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

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

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

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

Решим графическим методом задачу из примера 1.1.

Решение показано на рис. 1.1.

Рис. 1.1 Решение примера 1.1 графическим методом

Ограничение x 1 200 задается вертикальной линией x 1 =200. Все точки (x 1 ; x 2), расположенные справа от этой линии, удовлетворяют ограничению x 1 200, расположенные слева – не удовлетворяют. Ограничение x 2 100 задается горизонтальной линией x 2 =100. Все точки, расположенные сверху от этой линии, удовлетворяют ограничению x 2 100, расположенные снизу – не удовлетворяют.

Для построения линии, задающей ограничение 0,5x 1 +1,2x 2 600, удобно записать его в виде равенства: 0,5x 1 +1,2x 2 =600 . Выразим одну из переменных через другую: x 2 =-0,41x 1 +500. это уравнение прямой. Построим эту прямую. Она разбивает координатную плоскость на две полуплоскости. В одной из этих полуплоскостей находятся точки, удовлетворяющие ограничению, в другой – не удовлетворяющие. Чтобы найти полуплоскость, удовлетворяющую ограничению 0,5x 1 +1,2x 2 600, подставим в него координаты любой точки, например, (0; 0). Для этой точки ограничение выполняется. Значит, она находится в полуплоскости, удовлетворяющей ограничению.

Пересечение всех полуплоскостей, удовлетворяющих ограничениям задачи, представляет собой ОДР. На рис. 1.1 она выделена серым цветом.

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

Е(А) = 25∙200 + 40∙100=9000;

Е(В) = 25∙200 + 40∙416,67 = 21666,8;

Е(С) = 25∙960 + 40∙100 = 28000.

Таким образом, оптимальное решение находится в точке С= (960; 100). Это означает, что предприятию следует выпустить 960 т соляной кислоты и 100 т серной кислоты. Прибыль при этом составит 28000 ден.ед. Можно также найти количество опасных отходов, которое будет получено при производстве кислот: 0,5 960 + 1,2∙100 = 600 т.

Решим графическим методом задачу из примера 1.2. Решение показано на рис. 1.2.

Рис. 1.2 Решение задачи 1.2 графическим методом

В данном случае ОДР имеет только две угловые точки (А и В). Найдем для них значение целевой функции:

Е(А)= 0,5 ∙200+1,2 ∙ 375 =550;

Е (В) = 0,5 ∙640+1,2∙100 =440.

Таким образом, оптимальное решение находится в точке В(640; 100). Это означает, что предприятию следует выпустить 640 т соляной и 100 т серной кислоты. При этом образуется 440 т опасных отходов. Можно также найти прибыль от производства кислот: 25 ∙ 640 + 40 ∙100 = 20 000 ден.ед.

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

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

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

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

Теоретические основы графического метода

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

при которых линейная форма принимает оптимальное значение.

Пример 3.

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

Продолжаем решать задачи графическим методом вместе

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

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

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

Легко заметить, что функция F может неограниченно возрастать при заданной системе ограничений, поэтому можно условно записать, что .

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