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

Содержание

См. также: Решение задач симплекс методом

Описание метода

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(1.1) ;
(1.2)
Здесь , есть произвольные числа. Задача может быть как на нахождение максимума (max), так и на нахождение минимума (min). В системе ограничений могут присутствовать как знаки , так и знаки .

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

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

Так, первое неравенство
(1.2.1)
определяет полуплоскость, ограниченную прямой . С одной стороны от этой прямой , а с другой стороны . На самой прямой . Чтобы узнать, с какой стороны выполняется неравенство (1.2.1), мы выбираем произвольную точку, не лежащую на прямой. Далее подставляем координаты этой точки в (1.2.1). Если неравенство выполняется, то полуплоскость содержит выбранную точку. Если неравенство не выполняется, то полуплоскость расположена с другой стороны (не содержит выбранную точку). Заштриховываем полуплоскость, для которой выполняется неравенство (1.2.1).

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

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

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

Если хотя бы одно неравенство не выполняется, то выбираем другую точку. И так далее, пока не будет найдены одна точка, координаты которой удовлетворяют системе (1.2).

Нахождение экстремума целевой функции

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

Теперь мы можем искать экстремум целевой функции
(1.1) .

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

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

Если ОДР неограниченна, то может возникнуть случай, когда такую прямую провести нельзя. То есть как бы мы ни удаляли прямую от линии уровня (3) в сторону возрастания (убывания) , то прямая всегда будет проходить через ОДР. В этом случае может быть сколь угодно большим (малым). Поэтому максимального (минимального) значения нет. Задача решений не имеет.

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

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

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

Фирма выпускает платья двух моделей А и В. При этом используется ткань трех видов. На изготовление одного платья модели А требуется 2 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. На изготовление одного платья модели В требуется 3 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. Запасы ткани первого вида составляют 21 м, второго вида - 10 м, третьего вида - 16 м. Выпуск одного изделия типа А приносит доход 400 ден. ед., одного изделия типа В - 300 ден. ед.

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

Пусть переменные и означают количество произведенных платьев моделей А и В, соответственно. Тогда количество израсходованной ткани первого вида составит:
(м)
Количество израсходованной ткани второго вида составит:
(м)
Количество израсходованной ткани третьего вида составит:
(м)
Поскольку произведенное количество платьев не может быть отрицательным, то
и .
Доход от произведенных платьев составит:
(ден. ед.)

Тогда экономико-математическая модель задачи имеет вид:

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

Строим прямую .
При .
При .
Проводим прямую через точки (0; 7) и (10,5; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 10) и (10; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (8; 0).

Заштриховываем область, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.

(П1.1) .
При .
При .
Проводим прямую через точки (0; 4) и (3; 0).

Далее замечаем, что поскольку коэффициенты при и целевой функции положительны (400 и 300), то она возрастает при увеличении и . Проводим прямую, параллельную прямой (П1.1), максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку четырехугольника OABC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

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

.
То есть, для получения наибольшего дохода, необходимо изготовить 8 платьев модели А. Доход при этом составит 3200 ден. ед.

Пример 2

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

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

Строим прямую .
При .
При .
Проводим прямую через точки (0; 6) и (6; 0).

Строим прямую .
Отсюда .
При .
При .
Проводим прямую через точки (3; 0) и (7; 2).

Строим прямую .
Строим прямую (ось абсцисс).

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

Заштриховываем область по границам построенных прямых, чтобы точка (4; 1) попала в заштрихованную часть. Получаем треугольник ABC.

Строим произвольную линию уровня целевой функции, например,
.
При .
При .
Проводим прямую линию уровня через точки (0; 6) и (4; 0).
Поскольку целевая функция увеличивается при увеличении и , то проводим прямую, параллельную линии уровня и максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку треугольника АВC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

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

Пример отсутствия решения

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

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

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (2,667; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 3) и (6; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (3; 0) и (6; 3).

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

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

Заштриховываем область, чтобы точка (3; 3) попала в заштрихованную часть. Получаем неограниченную область, ограниченную ломаной ABCDE.

Строим произвольную линию уровня целевой функции, например,
(П3.1) .
При .
При .
Проводим прямую через точки (0; 7) и (7; 0).
Поскольку коэффициенты при и положительны, то возрастает при увеличении и .

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

Ищем минимум. Проводим прямую, параллельную прямой (П3.1) и максимально удаленную от нее в сторону убывания , и проходящую хотя бы через одну точку области ABCDE. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:

Максимального значения не существует.
Минимальное значение
.

См. также:

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

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

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

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

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

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

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

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

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

Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными. Рассмотрим задачу ЛП в стандартной форме:

max f(x 1 , x 2 , ..., x n) = ,

, i = 1, 2, …, m,

x j 0, j = 1, 2, …, n.

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

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

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

Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую об­ласть на плоскости. Определим, какую часть плоскости описыва­ет неравенство 2х 1 + Зх 2 12.

Во-первых, построим прямую 2х 1 + Зх 2 = 12. Она проходит через точки (6; 0) и (0; 4). Для того чтобы определить, какая полуплоскость удовлетворяет неравенству, необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет вы­полняться, то данная точка является допустимым решением, и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать точку начала координат. Подставим х 1 = х 2 = 0 в неравенство 2х 1 + Зх 2 12. Получим 2х0 + 3х0 12. Данное утверждение является верным, следовательно, неравенству 2х 1 + Зх 2 12 соответствует нижняя полуплоскость, содержащая точку (0; 0). Это отражено на графике, изображенном на рис. 1.1.

Аналогично графически можно изобразить все ограничения задачи ЛП.

Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений, или областью определения. Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (х j 0, j = 1, 2, …, n). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.

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

Этот вектор показывает направление наискорейшего измене­ния целевой функции. Прямая с 1 х 1 + с 2 х 2 = f(х 0) , перпендикуляр­ная вектору-градиенту, является линией уровня целевой функции. В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине «а» . Меняя значение «а», получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.

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

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

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

1. Строится многоугольная область допустимых решений (ОДР) ЗЛП.

2. Строится вектор-градиент целевой функции (ЦФ) в какой-нибудь точке х 0 , принадлежащей ОДР:

3. Линия уровня с 1 х 1 + с 2 х 2 = а (а - постоянная величина) - прямая, перпендикулярная вектору-градиенту , - передви­гается в направлении этого вектора в случае максимизации f(x 1 , х 2) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точ­кой максимума f(x 1 , х 2).

4. Для нахождения координат точки максимума достаточно решить два уравнения прямых, получаемых из соответствую­щих ограничений и дающих в пересечении точку максимума. Значение f(x 1 , х 2), найденное в получаемой точке, является мак­симальным.

При минимизации (максимизации) функции f(x 1 , х 2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимум (максимум) функ­ции f(x 1 , х 2) не существует.

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

Таблица 1.3

№	Вид ОДР	Вид оптимального решения	Примечания
	Многоугольная замкнутая	Единственное решение
	Единственное решение
	Многоугольная	ЦФ не ограничена снизу
	ЦФ не ограничена сверху
	Многоугольная незамкнутая	Единственное решение
	Бесконечное множество решений
	Отрезок	Единственное решение

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

Пример 1.1. Планирование выпуска продукции пошивочного предприятия (задача о костюмах).

Намечается выпуск двух видов костюмов – мужских и женских. На женский костюм требуется 1м шерсти, 2м лавсана и 1 чел./день трудозатрат. На мужской костюм – 3,5м шерсти, 0,5м лавсана и 1 чел./день трудозатрат. Всего имеется 350м шерсти, 240м лавсана и 150 чел./дней трудозатрат. Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского – 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Введем следующие обозначения: х 1 - число женских костюмов; х 2 – число мужских костюмов. Прибыль от реализации женских костюмов составляет 10х 1 , а от реализации мужских - 20х 2 , т.е. необходимо максимизировать целевую функцию:

10х 1 + 20х 2

Ограничения задачи имеют вид:

х 1 + х 2 150,

2 х 1 + 0,5х 2 240,

х 1 + 3,5х 2 350,

х 2 60,

х 1 0.

Первое ограничение по труду х 1 + х 2 150. Прямая х 1 + х 2 = 150 проходит через точки (150; 0) и (0; 150) (рис. 1.2).

Второе ограничение по лавсану 2 х 1 + 0,5х 2 240. Прямая 2 х 1 + 0,5х 2 = 240 проходит через точки (120; 0) и (0; 480). Третье ограничение по шерсти х 1 + 3,5х 2 350. Добавим четвертое ограничение по количеству мужских костюмов х 2 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х 2 = 60. На рис. 1.3 заштрихована область допустимых решений. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е.

Чтобы построить такой вектор, нужно соединить точку (10;20) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации – в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору . Так, на рис. 1.4 изображен вектор-градиент (30;60).

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

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

х 1 + 3,5х 2 = 350,

х 1 + х 2 = 150.

Отсюда легко записать решение исходной ЗЛП: max f(x) = 2300 и достигается при х 1 = 70 и х 2 = 80 (см. рис. 1.4).

1.3.ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ В СРЕДЕ EXCEL

1.3.1. Общие сведения о работе с табличным процессором Excel

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

Элементы экрана Excel. После запуска Excel на экране появля­ется таблица, вид которой показан на рис 1.5.

Это изображение называют рабочим листом. Оно представляет собой сетку строк и столбцов, пересечения которых образуют пря­моугольники, называемые ячейками. Рабочие листы предназначены для ввода данных, выполнения расчетов, организации информа­ционной базы и т.п. Окно Excel отображает основные программные элементы: строку заголовка, строку меню, строку состояния, кноп­ки управления окнами.

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

1) знака равенства;

2) совокупности значений или ссылок на ячейках, с которыми выполняются расчеты;

3) операторов.

4) Если знак равенства отсутствует, то Excel интерпретирует данные не как формулу, а как ввод данных в ячейку. Формулы можно вводить непосредственно в ячейку или в строку формул – как текст, так и число. При этом нужно выполнить следующие действия:

· выделить ячейку, которая должна содержать формулу и ввести знак (=);

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

· выделить другую ячейку, включаемую в формулу;

· нажать на клавишу Enter.

В строке формул появится введенная формула, в ячейке – результат расчета.

Использование в формулах функций. Чтобы облегчить ввод формул, можно воспользоваться функциями Excel. Функции - это встроенные в Excel формулы. Excel содержит множество формул. Они сгруппированы по различным типам: логические, математи­ческие, инженерные, статистические и др.

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

Различные функции выполняют разные типы вычислений по определенным правилам. Когда функция является единичным объектом в ячейке рабочего листа, она начинается со знака (=), далее следует название функции, а затем - аргументы функции, заключенные в скобки.

Поиск решения - это надстройка Excel, которая позволяет решать оптимизационные задачи. Если в меню Сервис отсутствует коман­да Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервис => Надстройки и активизируйте над­стройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и уда­ление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.

После выбора команд Сервис => Поиск решения появится диало­говое окно Поиск решения.

В диалоговом окне Поиск решения есть три основных пара­метра;

Установить целевую ячейку.

Изменяя ячейки.

Ограничения.

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

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

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

Для решения задачи необходимо:

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

2) ввести исходные данные;

3) ввести зависимость для целевой функции;

4) ввести зависимости для ограничении,

5) запустить команду Поиск решений;

6) назначить ячейку для целевой функции (установить целевую ячейку);

7) ввести ограничения;

8) ввести параметры для решения ЗЛП.

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

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

Пусть х 1 - число женских костюмов; х 2 - число мужских костюмов,

10 х х 1 + 20 х х 2 max

Ограничения задачи имеют вид:

х 1 + х 2 150 - ограничение по труду;

2 x х 1 + 0,5 х х 2 240 - ограничение по лавсану;

х 1 + 3,5 х х 2 350 - ограничение по шерсти;

х 2 60 - ограничение по мужским костюмам;

х 1 0 - ограничение по женским костюмам.

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

Обозначьте через x 1 , х 2 количество костюмов каждого типа. В нашей задаче оптимальные значения вектора = (х 1 , х 2) будут помещены в ячейках А2:В2, оптимальное значение целевой функ­ции - в ячейке СЗ.

2. Ввести исходные данные.

Введите исходные данные задачи, как показано на рис. 1.6.

3. Ввести зависимость для целевой функции.

· Поместить курсор в ячейку «СЗ», произойдет выделение ячейки.

· Поместить курсор на кнопку Мастер функций, расположенную на панели инструментов.

· Ввести Enter. На экране появляется диалоговое окно Мастер функ­ций шаг 1 из 2.

· В окне Функции выбрать строку СУММПРОИЗВ (рис. 1.7). На экране

· появляется диалоговое окно СУММПРОИЗВ (рис. 1.8).

· В строку Массив 1 ввести А2:В2 .

· В строку Массив 2 ввести АЗ:ВЗ.

Массив 1 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку. На рис. 1.9 показано, что в ячейку СЗ введена функция.

5. Ввести зависимости для ограничений (рис 1.10).

· Поместить курсор в ячейку СЗ.

· На панели инструментов кнопка Копировать в буфер.

· Поместить курсор в ячейку С4.

· Поместить курсор в ячейку С5.

· На панели инструментов кнопка Вставить из буфера.

· Поместить курсор в ячейку Сб.

· На панели инструментов кнопка Вставить из буфера.

· Поместить курсор в ячейку С7.

· На панели инструментов нажать кнопку Вставить из буфера. (Содержимое ячеек С4-С7 необходимо проверить. Они обяза­тельно должны содержать информацию, как это показано для примера на рис. 1.11; в качестве примера представлено содер­жимое ячейки С5.)

· В строке Меню указатель мышки поместить на Сервис. В развер­нутом меню выбрать команду Поиск решения. Появляется диа­логовое окно Поиск решения (рис. 1.12).

5. Запустить команду Поиск решения.

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

· Поместить курсор в строку Установить целевую ячейку.

· Ввести адрес ячейки $С$3.

· Ввести тип целевой функции в зависимости от условия вашей задачи. Для этого отметьте, чему равна целевая функция - Максимальному значению или Минимальному значению.

· Поместить курсор в строку Изменяя ячейки.

· Ввести адреса искомых переменных А$2:В$2 (рис. 1.13).

7. Ввести ограничения.

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

· Ввести знак ограничения.

· В строке Ограничение ввести адрес $D$4 (рис. 1.14).

· Поместить указатель мыши на кнопку Добавить. На экране вновь появится диалоговое окно Добавление ограничения.

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

· После введения последнего ограничения нажать на кнопку ОК. На экране появится диалоговое окно Поиск решения с введенны­ми условиями (рис. 1.15).

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

· В диалоговом окне поместить указатель мышки на кнопку Пара­метры. На экране появится диалоговое окно Параметры поиска решения (рис. 1.16).

· Установить флажки в окнах Линейная модель (это обеспечит применение симплекс-метода) и Неотрицательные значения.

· Поместить указатель мыши на кнопку ОК. На экране появится диалоговое окно Поиск решения.

· Поместить указатель Мыши на кнопку Выполнить.

Через непродолжительное время появятся диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками АЗ:ВЗ для значений х i и ячейка СЗ с максимальным значением целевой функции (рис. 1.17).

Если указать тип отчета Устойчивость, то можно получить до­полнительную информацию об оптимальном решении (рис. 1.18).

В результате решения задачи был получен ответ: необходимо сшить 70 шт. женских костюмов и 80 шт. мужских костюмов, чтобы получить максимальную прибыль 2300 у.е.

1.4. ДВОЙСТВЕННОСТЬ В ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. АНАЛИЗ ПОЛУЧЕННЫХ ОПТИМАЛЬНЫХ РЕШЕНИЙ

В 1975 г. наш соотечественник Л.В. Канторович был удостоен Нобелевской премии по экономике (совместно с американским экономистом Т. Купмансом) за разработку теории оптимального использования ресурсов (см. Приложение 1).

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

Переменные двойственной задачи y i называются объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

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

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

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

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная мат­рица А Т в двойственной задаче получаются друг из друга транс­понированием;

3) число переменных в двойственной задаче равно числу функци­ональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной;

4) коэффициентами при неизвестных в целевой функции двой­ственной задачи являются свободные члены в системе ограни­чений исходной задачи, а правыми частями в ограничениях двойственной задачи - коэффициенты при неизвестных в це­левой функции исходной; j 0.

Две приведенные задачи образуют пару симметричных двой­ственных задач. Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.

Первая теорема двойственности. Для взаимно двойственных за­дач имеет место один из взаимоисключающих случаев.

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

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

3. В двойственной задаче допустимое множество не пусто, а целе­вая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.

4. Обе из рассматриваемых задач имеют пустые допустимые мно­жества.

Вторая теорема двойственности (теорема о дополняющей неже­сткости). Пусть = (x 1 ,х 2 ,..., х п) - допустимое решение прямой задачи, a = (у 1 ,у 2 ,…,у т) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соот­ветственно прямой и двойственной задач, необходимо и достаточ­но, чтобы выполнялись следующие соотношения:

Условия (1.4) и (1.5) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное реше­ние другой задачи.

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

Теорема об оценках. Значения переменных y i в оптимальном реше­нии двойственной задачи представляют собой оценки влияния сво­бодных членов b i системы ограничений (неравенств) прямой задачи на величину

Решая ЗЛП симплекс-методом, мы одновременно решаем двой­ственную ЗЛП. Переменные двойственной задачи y i называют объективно обусловленными оценками.

Рассмотрим экономическую интерпретацию двойственной за­дачи на примере задачи о коврах.

Пример 1.2. Используя постановку задачи о коврах, выполнить следующие задания.

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

2. Используя Поиск решения, найти такой план выпуска продук­ции, при котором общая стоимость продукции будет макси­мальной.

3. Сформулировать экономико-математическую модель двой­ственной задачи к задаче о коврах.

4. Найти оптимальный план двойственной задачи, используя теоремы двойственности, пояснить равенство нулю Х 1 и Х 4 .

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

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

1. Сформулируем экономико-математическую модель задачи.

Обозначим через Х 1 , Х 2 , Х 3 , Х 4 число ковров каждого типа. Целевая функция имеет вид

F(X) = ЗХ 1 + 4Х 2 + ЗХ 3 + Х 4 max,

а ограничения по ресурсам

7Х 1 + 2Х 2 + 2Х 3 + 6Х 4 80,

5Х 1 + 8Х 2 + 4 Х 3 + ЗХ 4 480,

2Х 1 + 4 Х 2 + Х 3 + 8X 4 130,

Х 1 , X 2 , X 3 , Х 4 0.

2. Поиск оптимального плана выпуска.

Решение задачи выполним с помощью надстройки Excel Поиск решения. Технология решения задачи была подробно рассмотрена в задаче о костюмах. В нашей задаче оптимальные значения вектора Х=(Х 1 , X 2 , X 3 , Х 4) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции - в ячейке F4 .

Введем исходные данные. Сначала опишем целевую функцию с помощью функции - СУММПРОИЗВ (рис. 1.19). А потом введем данные для левых частей ограничений. В Поиске решения введем направление целевой функции, адреса искомых переменных, до­бавим ограничения. На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 1.20).

После ввода параметров для решения ЗЛП следует нажать кнопку Выполнить. На экране появится сообщение, что решение найдено (рис. 1.21).

Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы «труд» и «оборудование» будут использованы полностью, а из 480 кг пряжи (ресурс «сырье») будет использовано 280 кг.

Создание отчета по результатам поиска решения. Excel позволяет представить результаты поиска решения в форме отчета (табл. 1.4). Существует три типа таких отчетов:

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

· Устойчивость (Sensitivity). Отчет, содержащий сведения о чувстви­тельности решения к малым изменениям в изменяемых ячей­ках или в формулах ограничений.

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

Пример 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 и x 2 .

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

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

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

.

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вид сырья

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

Запас

А

Б

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 д.е.