Метод искусственного базиса

Кемеровский  филиал МЭСИ 
 
 
 
 
 
 

Курсовой  проект по

Математическим  методам. 
 
 
 
 
 
 
 
 
 
 
 
 

Кемерово 2012

Задание.

Для курсового  проектирования _______________________________________

___________________________________________________________________

Студента____________ курса, группы__________________________________

Ф.И.О.____________________________________________________________

Тема курсового  проекта______________________________________________

__________________________________________________________________

Для выполнения курсового проекта должны быть представлены

1. Введениея______________________________________________________________________________________________________________________________________________________________________________
2. Общая часть__________________________________________________ 
   ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
3. Специальная часть_____________________________________________ 
   ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
4. Графическая часть_____________________________________________ 
   __________________________________________________________________________________________________________________________
5. Используемая литература 
   _____________________________________________________________ 
   __________________________________________________________________________________________________________________________________________________________________________________________________

                

                 Дата выдачи___________________ 
                 Срок окончания________________ 
                 Руководитель 
                 курсового проекта_______________________________           

Содержание

1. Введение_____________________________________________2

2.  Линейное программирование _____________________________3

3.  Методы  решения задач_________________________________4

4.  Искусственный  базис____________________________________4

5.  Алгоритм метода искусственного базиса__________________6

6.  Блок  - схема___________________________________________7

7.  Задача_______________________________________________8

8.  Список  литературы____________________________________12 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. Введение.

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

     Свое  второе рождение линейное программирование получило в начале пятидесятых годов  с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и  американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".

     В автобиографии, представленной в Нобелевский  комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся  в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым  нужно было решить задачу о наиболее выгодном распределении материала  между станками. Эта задача сводилась  к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда… Поэтому простой перебор вершин не годился. Леонид Витальевич писал: "оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения". И уже летом 1939 года была сдана в набор книга Л.В.Канторовича "Математические методы организации и планирования производства", в которой закладывались основания того, что ныне называется математической экономикой.

     Американский  математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод  численного решения задач линейного  программирования (он получил название симплекс метода). Идеи линейного программирования в течении пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

     

     2. Линейное программирование.

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

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

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

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

• Задача называется стандартной, если система ограничений состоит только из неравенств.
• Задача называется канонической, если система ограничений состоит только из уравнений.
• Задача называется общей, если система ограничений состоит из уравнений и неравенств.  

 
 
 
 
 
 
 
 
 
 

3. Методы решения  задач.

Графический метод  решения  задач линейного  программирования.

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

 

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

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

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

4. Искусственный базис.

     Данный  метод решения применяется при  наличии в системе ограничений  и условий-равенств, и условий-неравенств, и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных R_i со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных, а в задачи минимизации - с положительными M. Таким образом из исходной получается новая M-задача (поэтому метод искусственного базиса так же называют M-методом).

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

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F, а другая – для составляющей M. При составлении симплекс таблицы полагают что исходные переменные являются небазисными, а дополнительные(x_n+m) и искусственные (R_i)- базисными.

Исходная  таблица для "Метода искусственного базиса" имеет следующий вид:

x1 x2 ... xn-1 xn b F -a0,1 -a0,2 ... -a0,n-1 -a0,n -b0 xn+1 a1,1 a1,2 ... a1,n-1 a1,n b1 xn+2 a2,1 a2,2 ... a2,n-1 a2,n b2 Ri ai,1 ai,2 ... ai,n-1 ai,n bi ... ... ... ... ... ... ... xn+m am,1 am,2 ... am,n-1 am,n bm M -∑ai,1 -∑ai,2 ... -∑ai,n-1 -∑ai,n -∑bi

Элементы дополнительной строки M расчитываются как сумма соответствующих коэффициентов условий-равенств (условий в которые после приведения к каноническому виду введены переменные R_i) взятая с противоположным знаком.

Правила преобразований симплексной  таблицы

При составлении  новой симплекс-таблицы в ней  происходят следующие изменения: 

• Вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_l записываем x_k.  
• ведущий элемент заменяется на обратную величину a_k,l'= 1/a_k,l
• все элементы ведущего столбца (кроме a_k,l) умножаются на -1/a_k,l
• все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l

оставшиеся  элементы симплекс-таблицы преобразуются  по формуле a_i,j'= a_i,j- a_i,l×a_k,j/ a_k,l 

5. Алгоритм метода  искусственного базиса.            

Шаг 1. Приводим задачу ЛП к каноническому виду с неотрицательными правыми частями   , i=1,..., m.            

            

Шаг 2. Строим вспомогательную задачу ЛП            

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

            

Шаг 3. Решаем ВЗЛП симплекс-методом.            

Шаг 4. Если   , то допустимого решения в исходной задаче не существует. Задача не разрешима и процесс решения исходной задачи завершается.             

Шаг 5. Если   , то строим СЗЛП для исходной задачи на основе оптимальной симплекс-таблицы ВЗЛП. Подготовительный этап симплекс-метода исходной задачи на этом завершается.

            Шаг 6. Определить ведущий элемент

           Шаг 7. Выполнить пересчёт матрицы

            Шаг 8. Проверить результат пресчёта атрицы на оптимальность

            Шаг 9. Если найденное решение оптимально,то вычисления прекратить и сформульровать ответ.