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

f = –х 1 + 5х 2 ¾> min ;

4х 1+ 3х 2 £ 24,

х 1– 10х 2 £ 0,

8х 1– 3х 2 ³ 0,

5х 1+ 3х 2 ³ 15,

х 1³0, х 2³ 0. (1)

Совокупность переменных хj , удовлетворяющих условию (1), называется областью допустимых решений. Допустимое решение, обращающее целевую функцию в min или max , называется оптимальным. Для его определения необходимо построить область допустимых решений (область определения). Так как в условии задачи заданы две переменные, то область допустимых решений находится на плоскости х 10х 2. Каждое неравенство (1) определяет полуплоскость, а равенство – прямую. Для построения полуплоскости необходимо найти ее границу и установить, с какой стороны от нее лежит искомая полуплоскость. Перепишем условия (1) в виде равенств (2) и пронумеруем их.

4х 1+ 3х 2	=	24 (I ),
х 1– 10х 2	=	0 (II ),
8х 1– 3х 2	=	0 (III ),
5х 1+ 3х 2	=	15 (IV ).	(2)

Введем систему координат х 10х 2 и построим последовательно эти прямые – границы полуплоскостей. Для построения прямой на плоскости необходимо определить любые две точки, лежащие на этой прямой. Если прямая пересекает оси 0х 1и 0х 2, то можно найти координаты точек ее пересечения с осями координат. Определим координаты пересечения прямой (I ) с осью 0х 1: х 1=0; Þ 3х 2= 24; Þ х 2= 8. Соответственно определим координаты второй точки пересечения первой прямой с осью 0х 2: х 2=0; Þ 4х 1= 24; Þ х 1= 6. Следовательно, точки пересечения прямой (I ) с осями координат равны (0,8) и (6,0). Построим эту прямую (рис. 1).

Определим полуплоскость. Для этого подставим в первое неравенство (1) координаты любой точки, не лежащей на данной прямой, например (0,0). Тогда из первого условия следует: 4×0+3×0 £24, значит, неравенство справедливо, откуда следует, что полуплоскость лежит с той стороны прямой, где находится точка с координатами (0,0).

Аналогичным образом строятся и другие полуплоскости. Необходимо учесть, что прямые (II) и (III) проходят через начало координат, т.е. точку (0,0). Координаты второй точки желательно брать пропорционально коэффициентам в уравнении искомой прямой. Например, для второй прямой – точки (0,0) и (10,1), а для третьей – (0,0) и (3,8). После построения всех полуплоскостей область допустимых решений примет следующий вид (рис. 3):

Целевая функция f определяет на плоскости прямую, которая должна проходить через точку или сторону многоугольника и иметь наименьшее значение. Построим направляющий вектор для этой прямой. Данный вектор перпендикулярен искомой прямой, и его направление всегда определяет максимум целевой функции. Противоположное направление вектора определяет минимум. Обозначим этот вектор через . Он проходит через точку (0,0) и (–1,5). Координаты второй точки берут из коэффициентов целевой функции и с их помощью определяют направление вектора. Перпендикулярно ему построим прямую –х 1+ 5х 2=0. Как было сказано выше, вектор всегда показывает направление возрастания значения целевой функции (max ) , противоположный ему вектор –– направление убывания значения целевой функции (min ). Перемещаем прямую –х 1+5х 2=0 по области определения параллельно самой себе в направлении min . Целевая функция f достигнет своего минимального значения в точке С (рис. 4).

Оптимальному решению задачи (1) соответствует точка С , которая лежит на пересечении прямых (I ) и (II ):

4х 1+ 3х 2= 24;

х 1– 10х 2= 0.

Для решения данной системы уравнений умножить второе уравнение на 4 и сложить соответственно по элементам с 1-м уравнением:

4х 1+ 3х 2 = 24;

4х 1– 40х 2 = 0.

Вычтем из первого уравнения второе, получим: 43х2= 24 Þ х 2= 0,56.

Подставив найденное значение х 2во второе уравнение, получим:

х 1= 10х 2Þ х 1=5,6. Подставив координаты точки С в целевую функцию, получим следующий результат:

f min = – 5,6 + 5×0,56 = – 2,8.

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

х 1= 5,6, х 2= 0,56;f min = – 2,8.

Решение данного примера на ПЭВМ осуществляется программным комплексом «Блок-3». С его помощью производятся ввод, решение и вывод результативной информации на внешний носитель. Простота и доступность комплекса позволит без труда освоить его и применять на практике.

Задача № 1.1.2.

f = 2х 1+ 3х 2 ¾> max;

2х 1+ 3х 2 £ 12,

2х 1– 5х 2 £ 0,

7х 1– 2х2³ 0,

х 1, х 2³ 0. (3)

Определения и построение области допустимых решений аналогичны заданию 1.1.1. Окончательный вид области допустимых решений представлен на рис. 5 многоугольником АВС (точка А совпадает с точкой 0).

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

угольника АВС . Для записи решения ЭММ необходимо найти координату x 1B – точки В и x 1C – точки С . Определив их, мы сможем найти отрезок, лежащий на оси 0x 1(рис. 6).

Координаты точки В – x1B определяются в результате пересечения прямых 2х 1+ 3х 2 = 12 и 7х 1– 2х 2 = 0. Для этого необходимо решить систему уравнений:

2х 1+ 3х 2= 12 ´ 2 Þ 4х 1+ 6х 2= 24;

7х 1– 2х 2= 0 ´ 3 Þ 21х 1– 6х2= 0.

Сложив два последних уравнения, получим: 25х 1=24, х 1=0,96. Из этого следует, что x 1B =0,96. Координата точки С – x 1C определяется в результате пересечения прямых 2х 1+ 3х 2=12 и 2х 1–5х 2=0. Решим систему уравнений:

2х 1+ 3х 2= 12 ´ 5 Þ 10х 1+ 15х 2= 60;

2х 1– 5х 2= 0 ´ 3 Þ 6х 1 – 15х 2= 0.

Сложив два последних уравнения, получим: 16х 1= 60, х 1= 3,75, откуда следует, что x 1C = 3,75.

Значение целевой функции для данной ЭММ равно 12 (так как уравнение прямой, на которой определен отрезок ВС – 2х 1+3х 2= 12).

Таким образом, ответ данной задачи:

x 1Î[x 1B ; x 1C ] Þ x 1Î;

2х 1+ 3х 2=12 Þ 3х 2= 12 – 2х 1Þ х 2= (12 – 2х 1)/3.

Полный ответ данного примера запишется в следующем виде:

x 1Î; x 2= (12 – 2х 1)/3; f max = 12.

Задача № 1.1.3.

f = 2х 1+ 3х 2 ¾> max;

2х 1+ 3х 2 ³ 12,

2х 1– 5х 2 £ 0,

7х 1– 2х 2³ 0,

х 1, х 2 ³0. (4)

Используя схему построения области допустимых решений задач 1.1.1–1.1.2, получим следующий график (рис. 7):

f = 2х 1+ 3х 2 ¾> max ;

х 1+ х2 £ 2,

2х 1+ 3х 2³ 12,

2х 1– 5х 2£ 0,

7х 1– 2х 2³ 0,

х 1, х 2³ 0. (5)

Используя график задачи 1.1.3 и достроив первую полуплоскость х 1+х2£ 2, получим область определения, показанную на рис. 8.

Из графика (рис. 8) видно, что для данной ЭММ области допустимых решений нет. Ответ: нет области допустимых решений.

Задача № 1.1.5.

f = – х 1+ 5х 2 ¾> min;

10х 1+ 3х 2£ 30,

10х 1+ 5х 2³ 50,

2х 1– 6х 2£ 0,

х 1, х 2³ 0. (6)

Область определения ЭММ (6) представлена на рис. 9. Из анализа графика следует, что областью допустимых решений будет являться точка А с координатами (0,10) (10х 1+ 5х 2= 50, х 1= 0, 5х 2= 50, х 2=10). В случае, когда решением ЭММ является единственная точка, целевую функцию можно не строить.

Ответ: x 1= 0; x 2=10; fmin = 0+5×10 = 50.

Таким образом, при решении задач ЭММ ЛП возможны следующие ситуации:

– задача имеет одно оптимальное решение;

– задача имеет бесконечное число оптимальных решений;

– задача не имеет оптимального решения;

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

На практике ЭММ ЛП не имеет решений только в том случае, если некорректна постановка задачи.

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

Задача № 1.1.6.

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

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

1) Решить графическим способом;

2) Решить на базе комплекса «Блок-3»;

3) Симплекс-методом.

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

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

Ответ

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

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

при ограничениях

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

Построим уравнение 3x 1 +x 2 = 9 по двум точкам .
Для нахождения первой точки приравниваем x 1 = 0. Находим x 2 = 9. Для нахождения второй точки приравниваем x 2 = 0. Находим x 1 = 3. Соединяем точку (0;9) с (3;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 3 . 0 + 1 . 0 - 9 ≤ 0, т.е. 3x 1 +x 2 - 9≥ 0 в полуплоскости выше прямой.
Построим уравнение x 1 +2x 2 = 8 по двум точкам .
Для нахождения первой точки приравниваем x 1 = 0. Находим x 2 = 4. Для нахождения второй точки приравниваем x 2 = 0. Находим x 1 = 8. Соединяем точку (0;4) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 . 0 + 2 . 0 - 8 ≤ 0, т.е. x 1 +2x 2 - 8≥ 0 в полуплоскости выше прямой.
Построим уравнение x 1 +x 2 = 8 по двум точкам .
Для нахождения первой точки приравниваем x 1 = 0. Находим x 2 = 8. Для нахождения второй точки приравниваем x 2 = 0. Находим x 1 = 8. Соединяем точку (0;8) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 . 0 + 1 . 0 - 8 ≤ 0, т.е. x 1 +x 2 - 8≤ 0 в полуплоскости ниже прямой.

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

Проверить правильность построения графиков функций можно с помощью калькулятора

Рассмотрим целевую функцию задачи F = 4x 1 +6x 2 → min.
Построим прямую, отвечающую значению функции F = 0: F = 4x 1 +6x 2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора - точка (0; 0), конец - точка (4; 6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = 4x 1 +6x 2 пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (2) , то ее координаты удовлетворяют уравнениям этих прямых:
3x 1 +x 2 =9
x 1 +2x 2 =8

Решив систему уравнений, получим: x 1 = 2, x 2 = 3
Откуда найдем минимальное значение целевой функции:
F(X) = 4*2 + 6*3 = 26

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

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

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

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

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

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

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

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

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

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

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

I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

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

Если неравенство истинное,

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

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

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

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

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

IV. Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V. Построить вектор, который начинается в точке (0;0) и заканчивается в точке. Если целевая прямая и вектор построены верно, то они будут перпендикулярны .

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

VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится.

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

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

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