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

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

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

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

Оптимизация – целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

· количество продукции - расход сырья

· количество продукции - качество продукции

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

При постановке задачи оптимизации необходимо:

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

Типичный пример неправильной постановки задачи оптимизации:

«Получить максимальную производительность при минимальной себестоимости».

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

Правильная постановка задачи могла быть следующая:

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности;

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

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

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

Учёт ограничений.

 

 

1. Теоретическая часть.

 

Глава 1. Простой симплекс-метод.

 

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

Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1 , X2 , Xn , удовлетворяющих ограничениям в виде равенств:

A11X1 + A12X2 + … + A1nXn = B1;

A21X1 + A22X2 + … + A2nXn = B2;

……………………………………

Am1X1 + Am2X2 + … + AmnXn = Bm;

Xj ≥ 0, j =1,…, n

и обращающих в максимум линейную функцию этих переменных:

E = C1X1 + C2X2 + … + CnXn Þ max

При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия:

Bj ≥ 0, j=1,…,n

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

- перейти от минимизации целевой функции к ее максимизации;

- изменить знаки правых частей ограничений;

- перейти от ограничений-неравенств к равенствам;

- избавиться от переменных, не имеющих ограничений на знак.

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

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

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

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

ѓ = C0 + C1x1 + C2x2 +...+ Cnxn

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

a11x1 + a12x2 +...+ a1nxn = b1

a21x1 + a12x2 +...+ a2nxn = b2

...

am1x1 +am2x12 +...+ amnxn = bm

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

ѓ - C1x1-C2x2 -...-Cnxn = C0

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

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

x1 +...+ a1,r+1xr+1 +...+ a1nxn = b1

x2 + a2,r+1xr+1 +...+ a2nxn = b2

...

xr+ ar,r+1xr+1 +...+ arnxn = br

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

ѓ + Cr+1xr+1 + Cr+2xr+2 -...- Cnxn = C0

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

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

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

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