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

Пример 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-документа:

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

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

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

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

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(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. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:

Ответ

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

Графический метод решения ЗЛП основан на утверждениях, приведенных в пункте 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 и Изделие 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 ден.ед.

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

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

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

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

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

В математически формализованной системе анализа, планирования и управления особое место занимают сетевые графики. Они дают большой экономический эффект при строительстве и монтаже промышленных и других предприятий.
Сетевой график (рис. 6.1) позволяет выделить из всего комплекса работ наиболее важные, лежащие на критическом пути, и сосредоточить на них основные ресурсы строительномонтажных организаций, устанавливать взаимосвязь между различными специализированными организациями и координировать их работу. Работы, лежащие на критическом пути, требуют наиболее продолжительного ожидания поступления очередного события. На стадии оперативного анализа и управления сетевой график дает возможность осуществлять действенный контроль за ходом строительства, своевременно принимать меры по устранению возможных задержек в работе.
Применение сетевых графиков анализа, планирования и управления обеспечивает, как показывают многие примеры, сокращение сроков строительства на 20-30%, повышение производительности труда на 15-20%.
При анализе, осуществляемом непосредственно на стройках, использование материалов сетевого планирования и управления способствует правильному определению причин, влияющих на ход строительства, и выявлению предприятий, не обеспечивающих выполнение порученных им работ или поставку оборудования в сроки, установленные графиком.
Разработка сетевого графика в строительстве осуществляется при наличии: норм продолжительности строительства и срока ввода в действие объекта или комплекса объектов, проектно-сметной документации, проекта организации строительства и производства работ, типовых технологических карт, действующих норм затрат труда, материалов и работы машин. Кроме того, при составлении графика используются опыт выполнения отдельных работ, а также данные о производственной базе строительных и монтажных организаций.
На основе всех этих данных составляется таблица работ и ресурсов, где в технологической последовательности производства работ указываются их характеристика, объем, трудоемкость в человеко-днях, исполнитель (организация и бригада), численность рабочих, сменность, потребность в механизмах и материалах, источники их поступления, общая продолжительность выполнения работы в днях, а также предшествующее задание, после окончания которого можно начинать данную работу. Исходя из показателей такой таблицы, подготавливают сетевой график, который может иметь различную степень детализации в зависимости от принятой схемы произ
водства работ и уровня руководства; кроме общего графика исполнители разрабатывают график выполняемых ими работ.
Основные элементы сетевого графика: событие, работа, ожидание, зависимость.
При анализе хода строительства объекта следует устанавливать, правильно ли составлен сетевой график, не допущено ли при этом завышение критического пути, учтены ли при оптимизации графика все возможности его сокращения, нельзя ли какие-либо работы выполнять параллельно или сократить время, затрачиваемое на них, путем увеличения средств механизации и др. Это особенно важно в тех случаях, когда продолжительность работ по графику не обеспечивает окончание строительства в срок.
Основным материалом сетевого планирования, используемого при анализе, является информация о ходе работ по графику, который обычно составляется не реже одного раза в декаду. В качестве примера приводится карта задания и информации о ходе работы по объекту строительства, осуществляемому по сетевому графику (табл. 6.1). По данным карты, критические работы выполнялись в начале месяца с опережением графика, однако затем было допущено отставание монтажа подкрановых балок по ряду Б, а последующая работа - монтаж подкрановых балок по ряду А - закончена с отставанием на один день.
Оптимизация сетевых графиков осуществляется на стадии планирования посредством сокращения критического пути, т. е. минимизации сроков выполнения строительных работ при заданных уровнях ресурсов, минимизации уровня потребления материальных, трудовых и финансовых ресурсов при фиксированных сроках выполнения строительных работ. Возможен и смешанный подход: для одной части работ (более дорогостоящих) - минимизировать уровень потребления ресурсов при фиксированных сроках выполнения работ, для другой - минимизировать сроки при фиксированном уровне ресурсов.
Решение оптимизационных задач существенно облегчается наличием пакетов прикладных программ (ППП), приспособленных к составлению оптимальных сетевых графиков на ЭВМ.
В зарубежной практике системного анализа распространен графо-математический метод, получивший название «дерево решений». Суть этого метода заключается в следующем.
Путем предварительной оценки потребностей, предварительного анализа возможных организационных, технических или технологических условий намечаются все предполагаемые варианты решения данной задачи. Вначале разрабатываются

	Задание					Информация				Резерв времени по работам		Чис тый
Наименование работ	шифр	дата начала	дата оконча	плановая продол	Ре зерв вре	% тех-	требуемое время для	при чина	фактическая дата	находя щимся	не находящимся	резерв времени с
	работ	работ (план)	ния работ (план)	житель ность, дней	мени	кой готов ности	оконча ния работ, дней	задер жки	оконча ния работ	на критическом пути	аа критическом пути	начала месяца, дней
1	2	3	4	5	6	7	8	9	10	11	12	13
Разработка грунта	1-2	1/IV	6/IV	5	0	100	-	-	6/IV	¦-	-	-
Бетонирование фундаментов под котлы	2-3	7/IV	17/1V	9	0	100	14/IV	2	2
Бетонирование фундаментов по ряду А	2-4	7/IV	14/1V	7	2	100	14/IV
То же по ряду Б	2-5	7/IV	14/IV	7	2	100	-	-	14/IV
Устройство трубной разводки	6-18	18/IV	21/IV	4	19	100	-	-	29/IV	-7
Устройство обратной засыпки	6-7	18/IV	19/IV	2	0	100	17/IV	2	2
Монтаж сборных железобетонных ко
лонн: по ряду Б	7-8	20/IV	22/IV	3	1	100	-	-	22/IV	_	-	-
по ряду А	7-9	20/IV	22/IV	3	1	100	-	-	22/IV	-	-	-

Устройство подкрановых путей и монтаж башенного крана 7-10
Установка опорных рам на фундамент под оборудование 7-16 Монтаж подкрановых балок:
по ряду Б 8-11
20/IV 24/IV 4
20/IV 24/IV 4
24/IV 25/IV 2

по ряду А 10-12 25/IV 26/IV
Монтаж первой части балок и плит покрытия 12-13 27/IV 4/V
Монтаж подкрановых путей мостового lt;3 крана 12-14 27/IV 3/V

6	7	8	9	10	11	12	13
0	100	-	-	22/IV	1	-	1
14	100.	-	-	29/IV	-	-5	-
1	100	за-	27/IV	-2

27/IV -1
держ- ка с поставкой ж/б конструкций

1. 100 -

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