Симплекс-метод, его сущность

Содержание. 

Введение……………………………………………………………………………………….с.5.

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

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

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

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

1.3 Алгоритм симплекс-метода…………………………………………………с.10.

1.4 Решение задачи оптимизации. Построение аналитической модели……...с.12.

1.5 Приведение задачи к стандартной форме. Определение начального допустимого решения…………………………….……………………………...с.14.

Глава 2. Двухэтапный  метод.

2.1 Искусственное  начальное решение…………………………………………с.16.

2.2 Алгоритм  двухэтапного метода……………………………………………..с.19.

Глава 3. Особые случаи симплекс-метода……………………………………………...23.

3.1 Вырожденность……………………………………………………………....с.24.

3.2 Альтернативные  оптимальные решения…………………………………....с.27.

3.3 Неограниченные  решения…………………………………………………...с.30.

3.4 Отсутствие  допустимых решений…………………………………………..с.32.

2. Практическая часть.

2.1 Постановка  задачи…………..……………………………………………………..с.34.

2.2 Решение…..…………………………………………………………………………с.36.

Заключение…………………………………………………………………………………...с.39.

Литература…………………………………………………………………………………....с.40. 
 
 
 
 
 
 
 

Введение. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     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 

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

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

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

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

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

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

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

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

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

     ѓ = 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. Составляют симплекс-таблицу. В общем виде: 

 

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

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

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

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