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

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

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

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

Для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 Задача №2 для самостоятельного решения

При изготовлении изделий И1 и И2 используются сталь и цветные металлы а также токарные и фрезерные станки. По технологическим нормам на производство единицы изделия И1 требуется Т1 и Ф1 станко-часов соответственно токарного и фрезерного оборудования, а также С1 и Ц1 кг соответственно стали и цветных металлов. Для производства единицы изделия И2 требуется Т2, Ф2, С2 и Ц2 соответствующих единиц тех же ресурсов.

Цех располагает ФТ и ФФ станко-часами соответственно токарного и фрезерного оборудования и ФС и ФЦ кг соответственно стали и цветных металлов. Прибыль от реализации единицы изделия И1 составляет 6 руб., и от единицы изделия И2 – 16 руб.

№ варианта	Т1	Ф1	С1	Ц1	Т2	Ф2	С2	Ц2	ФТ	ФФ	ФС	ФЦ
1	300	200	10	20	400	100	70	50	13000	7000	650	850
2	315	200	11	20	405	101	71	50	13000	7000	600	850
3	320	200	12	20	410	102	72	50	13000	7000	600	850
4	305	200	13	20	415	104	73	50	13000	7000	600	850
5	322	200	14	20	420	103	74	50	13000	7000	600	850
6	298	200	15	20	425	105	75	52	12000	6800	650	880
7	280	200	9	20	430	103	70	52	12000	6800	650	880
8	290	200	8	22	395	98	71	52	12000	6800	650	880
9	295	200	10	24	390	98	72	52	12000	6800	650	880
10	285	200	11	25	385	97	73	52	12000	6800	650	880
11	275	200	14	23	390	99	74	4	12500	6800	650	900
12	305	200	8	21	395	99	75	48	12500	6800	680	900
13	308	200	9	22	400	97	68	48	12500	6800	680	900
14	312	200	9	18	410	98	67	48	12500	6800	680	900
15	300	200	13	19	405	100	69	48	12500	6800	680	900