Лабораторная работа № 4 Решение задач оптимизации симплекс-методом

 

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

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

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

 

ƒ = C₀ + C₁x₁ + C₂x₂ +...+ C_nx_n

 

и система m линейных уравнений с n неизвестными. Это называется системой ограничений:

a₁₁x₁ + a₁₂x₂ +...+ a_1nx_n = b₁

a₂₁x₁ + a₁₂x₂ +...+ a_2nx_n = b₂

...

a_m1x₁ +a_m2x₁₂ +...+ a_mnx_n = b_m

 

 

Целевую функцию представим в виде:

 

ƒ - C₁x₁-C₂x₂ -...-C_nx_n = C₀

 

Составим симплекс-таблицу.В дальнейшем будем считать, что ранг матрицы системы ограничений равен r. В системе ограничений выбран базис (основные неизвестные) x1,x2,...xn и коэффициенты в правой части не отрицательны.

В этом случае система ограничений будет иметь вид:

x₁ +...+ a_1,r+1x_r+1 +...+ a_1nx_n = b₁

x₂ + a_2,r+1x_r+1 +...+ a_2nx_n = b₂

...

x_r+ a_r,r+1x_r+1 +...+ a_rnx_n = b_r

 

 

Тогда целевая функция имеет вид:

ƒ + C_r+1x_r+1 + C_r+2x_r+2 -...- C_nx_n = C₀

Нахождение оптимального плана симплекс-методом включает следующие этапы:

1. Находят опорный план.

2. Составляют симплекс-таблицу. В общем виде:

 

 

Базисные неизвестные	Свободные члены	x1	x2	...	xr	xr+1	xj	xn
x1 x2 ... xi ... xr	b1 b2 ... bi ... br	... ...			... ...	a1,r+1 a2,r+1 ... ai,r+1 ... ar,r+1	a1j a2j ... aij ... arj	a1n a2n ... ain ... arn
ƒ	C0			...		Cr+2	Cj	Cn

 

 

3. В нижней строчке симплекс-таблицы необходимо отыскать отрицательные числа (не считая коэффициент С_о). Если таких чисел нет, то данное базисное решение является оптимальным.

4. Пусть элемент С_j<0,тогда в j-ом столбце необходимо найти положительный элемент. Если все коэффициенты этого столбца отрицательные, то решения не существует.

5. Если положительный коэффициент в j-ом столбце один, то выбранную строку с номером i надо поделить все коэффициенты на число a_ij.Результат деления записываем в новую симплекс-таблицу. Если же положительных коэффициентов несколько, необходимо составить отношение b_i/a_ij и из полученных значений выбрать наименьшее, соответствующее i-ой строке.

6. В новой симплекс-таблице в столбце базисных неизвестных вместо x_i пишется x_j. Продолжается заполняться таблица. В столбце с номером j необходимо получить нули(включая строку с целевой функцией). Для этого надо умножить i-ую записанную строку на нужное число и сложить с остальными строками.

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