Файл: Сущность математического программирования 5 1 Линейное программирование 5.docx

X нач  = ( 0 , 0 , 0 , 25 , 20 , 18 )

Вернемся  к рассмотрению функции L.

L =    6 x1  + 5 x2  + 9 x3

Функция L не содержат базисных переменных.

Для составления начальной симплекс таблицы мы выполнили все условия.

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

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

Шаг 1

За  ведущий выберем столбец 3 , так  как -9 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу  свободных членов не рассматриваем.

За  ведущую выберем строку 3, так  как отношение свободного члена  к соответствующему элементу выбранного столбца для 3 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 3.

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены	Отношение
X4	5	2	3	1	0	0	25	25/3
X5	1	6	2	0	1	0	20	10
X6	4	0	3	0	0	1	18	6
L	-6	-5	-9	0	0	0	0	-

Разделим  элементы строки 3 на 3.

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены	Отношение
X4	5	2	3	1	0	0	25	25/3
X5	1	6	2	0	1	0	20	10
X6	4/3	0	1	0	0	1/3	6	6
L	-6	-5	-9	0	0	0	0	-

---

От  элементов строки 1 отнимает соответствующие элементы строки 3, умноженные на 3.

От  элементов строки 2 отнимает соответствующие  элементы строки 3, умноженные на 2.

От  элементов строки L отнимает соответствующие элементы строки 3, умноженные на -9. 

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены
X4	1	2	0	1	0	-1	7
X5	-5/3	6	0	0	1	-2/3	8
X6	4/3	0	1	0	0	1/3	6
L	6	-5	0	0	0	3	54

X1 = ( 0 , 0 , 6 , 7 , 8 , 0 ) L =    54 - 6 x1  + 5 x2  - 3 x6

Значение  функции L для данного решения: L (X1) = 54

Шаг 2

За  ведущий выберем столбец 2 , так  как -5 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем.

За  ведущую выберем строку 2, так  как отношение свободного члена  к соответствующему элементу выбранного столбца для 2 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 2.

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены	Отношение
X4	1	2	0	1	0	-1	7	7/2
X5	-5/3	6	0	0	1	-2/3	8	4/3
X6	4/3	0	1	0	0	1/3	6	-
L	6	-5	0	0	0	3	54	-

---

     Разделим  элементы строки 2 на 6.

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены	Отношение
X4	1	2	0	1	0	-1	7	7/2
X5	-5/18	1	0	0	1/6	-1/9	4/3	4/3
X6	4/3	0	1	0	0	1/3	6	-
L	6	-5	0	0	0	3	54	-

От  элементов строки 1 отнимает соответствующие  элементы строки 2, умноженные на 2.⁹

От  элементов строки L отнимает соответствующие  элементы строки 2, умноженные на -5.

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены
X4	14/9	0	0	1	-1/3	-7/9	13/3
X5	-5/18	1	0	0	1/6	-1/9	4/3
X6	4/3	0	1	0	0	1/3	6
L	83/18	0	0	0	5/6	22/9	182/3

X2 = ( 0 , 4/3 , 6 , 13/3 , 0 , 0 ) L =    182/3  - 83/18 x1 - 5/6 x5  - 22/9 x6

Значение  функции L для данного решения: L (X2) = 182/3

Учитывая, что все xi  ≥ 0, по условию задачи, наибольшее значение функции L равно свободному члену 182/3, т.е. мы получили оптимальное решение.

---

Ответ: X опт = (0 , 4/3 , 6 , 13/3 , 0 , 0);  Значение функции: L = 182/3 

---

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

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

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

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

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

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

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

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

---