Основы математического программирования (стр. 7 )

Можно выписать ответ. Значения базисных переменных и целевой функции выписываются из столбца свободных членов. Все небазисные переменные равны 0.

x1 = 100

x2 = 1

x3 = 26/10

x4 = 0

x5 = 0

x6 = 72/10

x7 = 0

Z max = 3703,6

_________________________________________________________________

Определения:

Базисными переменными системы ограничений из n уравнений в задаче линейного программирования называются некоторые r переменных, которые можно выразить через остальные n-r, называемых свободными, где r – ранг матрицы системы.

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

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

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

Допустимым базисным решением или опорным называется решение, в котором значения переменных неотрицательны.

Переменными задачи называются величины х1, х2, ,,,, хn, которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора. Х = (х1, х2, ,,,, хn).

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

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

Основные теоремы, на которых основан симплекс-метод:

1. Целевая функция задачи линейного программирования достигает экстремума в угловой точке области допустимых решений.

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

Основная задача линейного программирования.

Общая задача линейного программирования.

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

Этапы построения математической модели.

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

Линейное программирование – это задача математического программирования, в которой и целевая функция, и система ограничений линейны.

2.7. Характеристика особых случаев симплекс-метода

1. Случай вырожденности.

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

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

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

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

2. Система ограничений противоречива.

В таблице недопустимый вариант – в строке с отрицательным свободным членом все коэффициенты положительные, следовательно, симплексное отношение будет отрицательным

В данном случае задача не имеет решения.

3. В системе ограничений не ограничен расход какого-либо ресурса.

В выбранном разрешающем столбце все коэффициенты будут отрицательными.

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

4. Система ограничений содержит строгие равенства и неравенства. (Смешанная система ограничений).

Сначала в качестве разрешающей строки взять строку, в которой записано строгое равенство. Разрешающий элемент в этой строке выбирается произвольно.

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

Такую процедуру повторить для каждого строгого равенства до их полного исключения. Затем в силу вступает симплекс-метод.

Пример 1. (случай вырожденности)

Zmax = 5x1+ 10x2 +3x3 + 4 x4

x1 + x2 + 2x3 + x4 ≤ 15

x1 + x2 + x3 + x4 ≤ 20

2x1 + 3 x2 ≥ 3x3 + 4x4

Решение:

Zmax - 5x1 - 10x2 -3x3 - 4 x4 = 0

x1 + x2 + 2x3 + x4 + у1 = 15

x1 + x2 + x3 + x4 + у2 = 20

- 2x1 - 3x2 + 3x3 + 4x4 +у3 = 0

Баз. перемен.	Своб. члены	y1	y2	y3	х1	х2 *	x3	x4
у1 *	15	1	0	0	1	1	2	1
у2	20	0	1	0	1	1	1	1
y3	0	0	0	1	-2	-3	3	4
Z	0	0	0	0	-5	-10	-3	-4

Баз. перемен.	Своб. члены	y1	y2	y3	х1	х2	x3	x4
x2	15	1	0	0	1	1	2	1
у2	5	-1	1	0	0	0	-1	0
y3	45	3	0	1	1	0	9	7
Z	150	10	0	0	5	0	17	6

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

Можно выписать ответ. Значения базисных переменных и целевой функции выписываются из столбца свободных членов. Все небазисные переменные равны 0.