Решение исходной задачи симплексным методом

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

Полученная модель является задачей линейного программирования, функция F – целевая функция. Она является линейной функцией своих переменных (х₁,х₂), ограничения на эти переменные тоже являются переменными.

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

Приведем систему к каноническому виду. Для этого введем балансовые переменные- х₃, х₄, х₅ и получим модель в следующем виде:

3x₁ +2х₂+х₃ = 32

4x₁ + 5х₂ +х₄= 48

x₁ + 6х₂ +х₅= 40

х_i≥0, _i=1..5.

F= 6x₁ + 11х₂ →max.

Запишем данную задачу в исходную симплексную таблицу:

Сi	Базис (xi)	Ai0	х1	х2	х3	х4	х5
	х3
	х4
	х5
	F		-6	-11

Первые три строки этой таблицы содержат в условной форме систему ограничений, а именно в столбце a_{i 0} - записываются свободные члены уравнений. В столбцах х₁, х₂, х₃, х₄, х₅ – записываются коэффициенты при соответствующих переменных этой системы.

Слева от столбца a_i0 , в столбце (х_i), записываются базисные переменные (которые ввели для баланса), содержащиеся в соответствующих уравнениях системы. Верхняя строка и крайний верхний столбец содержат коэффициенты при соответствующих переменных в целевой функции.

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

а₀₀ = 0∙32+0∙48+0∙40=0

Остальные значения обозначаются а_0k, получаются в результате скалярного умножения вектора столбца Сi на вектор столбец коэффициента при неизвестном x_k c последующим вычитанием соответствующего элемента верхней строки, например: а₀₁=(0∙3+0∙4+0∙1)-6 = -6

Для получения оптимального плана необходимо, чтобы все элементы оценочной строки симплексной таблицы были неотрицательными. Для этого:

1. выбираем в исходной таблице разрешающий столбец- p. Этот столбец соответствует наибольшей по абсолютной величине отрицательной оценке. В данной задаче это будет столбец х₂ (т.к |-6| < |-11|).

2. выбираем в исходной таблице разрешающую строку – q., используя условие

, т.е. 32/2=16, 48/5=9,6, 40/6=6,66(min)

На перекрестке разрешающей строки и разрешающего столбца, получим разрешающий элемент - а_qp. В данной задаче разрешающим элементом будет являться 6.

Сi	Базис (xi)	Ai0	х1	х2	х3	х4	х5
	х3
	х4			5
	х5							q
	F		-6	-11
				p

3. В новой симплексной таблице элементы разрешающей строки пересчитываем по формуле:

На месте разрешающего элемента ставим 1, в разрешающем столбце все элементы заменяем на - 0. остальные элементы и элементы оценочной строки пересчитываем по формуле прямоугольников:

Расчет по формуле прямоугольников представлен в таблице

Сi	Базис (xi)	Ai0	х1	х2	х3	х4	х5
	х3
	х4
	х2
	F

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

: =7

: = (min)

: = 40

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

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

Получим таблицу

Сi	Базис (xi)	Ai0	х1	х2	х3	х4	х5
	х3
	х1
	х2
	F

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

Оптимальное решение получаем в виде вектора

x_опт = (х₁, х₂, х₃, х₄, х₅)

F_max = 92,63

Оптимальное решение к исходной задаче получается отбрасыванием из x_опт компонент, связанными с балансовыми переменными х₃, х₄, х_5, т.е

x_опт =(, )

F_max = ∙6-11∙ = =92,63

Следовательно, фабрике необходимо выпускать единицы продукции вида А и единицы продукции вида В, при этом максимальная прибыль составляет 92,63 тысячи рублей.

Дата добавления: 2015-04-25