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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Быстрая помощь студентам

 

Результат поиска


Наименование:


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

Информация:

Тип работы: курсовая работа. Добавлен: 13.06.13. Сдан: 2012. Страниц: 12. Уникальность по antiplagiat.ru: < 30%

Описание (план):


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

Курсовой  проект по
Математическим  методам. 
 
 
 
 
 
 
 
 
 
 
 
 

Кемерово 2012
Задание.
Для курсового  проектирования _______________________________________
___________________________________________________________________
Студента____________ курса, группы__________________________________
Ф.И.О.____________________________________________________________
Тема курсового  проекта______________________________________________
__________________________________________________________________
Для выполнения курсового проекта должны быть представлены
    Введениея______________________________________________________________________________________________________________________________________________________________________________
    Общая часть__________________________________________________ 
    ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

    Специальная часть_____________________________________________ 
    ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

    Графическая часть_____________________________________________ 
    __________________________________________________________________________________________________________________________

    Используемая литература 
    ____________________________________________________________
    __________________________________________________________________________________________________________________________________________________________________________________________________

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


Содержание
    Введение_____________________________________________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со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных, а в задачи минимизации - с положительными M. Таким образом из исходной получается новая M-задача (поэтому метод искусственного базиса так же называют M-методом).
     Если  в оптимальном решении М-задачи нет искусственных переменных, это  решение есть оптимальное решение  исходной задачи. Если же в оптимальном  решении M-задачи хоть одна из искусственных  переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.
Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F, а другая – для составляющей M. При составлении симплекс таблицы полагают что исходные переменные являются небазисными, а дополнительные(xn+m) и искусственные (Ri)- базисными.
Исходная  таблица для "Метода искусственного базиса" имеет следующий вид:
  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 расчитываются как сумма соответствующих коэффициентов условий-равенств (условий в которые после приведения к каноническому виду введены переменные Ri) взятая с противоположным знаком.
Правила преобразований симплексной  таблицы
При составлении  новой симплекс-таблицы в ней  происходят следующие изменения: 
    Вместо базисной переменной xзаписываем xl; вместо небазисной переменной xзаписываем xk.  
    ведущий элемент заменяется на обратную величину ak,l'= 1/ak,l
    все элементы ведущего столбца (кроме ak,l) умножаются на -1/ak,l
    все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l
оставшиеся  элементы симплекс-таблицы преобразуются  по формуле ai,j'= ai,j- ai,l?ak,j/ ak,l 

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

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

и приводим ее к  специальному виду. Для этого целевую  функцию выражаем через небазисные переменные.
            
Шаг 3. Решаем ВЗЛП симплекс-методом.            
Шаг 4. Если   , то допустимого решения в исходной задаче не существует. Задача не разрешима и процесс решения исходной задачи завершается.             
Шаг 5. Если   , то строим СЗЛП для исходной задачи на основе оптимальной симплекс-таблицы ВЗЛП. Подготовительный этап симплекс-метода исходной задачи на этом завершается.
            Шаг 6. Определить ведущий элемент
           Шаг 7. Выполнить пересчёт матрицы
            Шаг 8. Проверить результат пресчёта атрицы на оптимальность
            Шаг 9. Если найденное решение оптимально,то вычисления прекратить и сформульровать ответ. 
 
 
 
 
 


    Блок  схема.

 
 

 
 


 





 


 





 

 

 



 


 
 


    Задача.
  
 
 

искусственные, базисные переменные. 
 
 
 
 

      X1 X2 X3 X4 X5      
      Z 0 -2 -1 -6 12 9 0 0 0
        13 1 1 7 -3 -7 1 0 0
        20 1 2 13 2 -14 0 1 0
        19 1 3 20* 6 -23 0 0 1
        M -52 -3 -6 -40 -5 44 0 0 0

 
X1 = ( 0 , 0 , 0 , 0 , 0 , 13 , 20 , 19 )
min
Элементы строки r3 разделим на 20.
      X1 X2 X3 X4 X5      
      Z 0 -2 -1 -6 12 9 0 0 0
        13 1 1 7 -3 -7 1 0 0
        20 1 2 13 2 -14 0 1 0
              1*     0 0  
      M -52 -3 -6 -40 -5 44 0 0 0

 
Убираем искусственную переменную r3, заменяем ее на базисную переменную X3.
Пересчитываем таблицу. 

      X1 X2 X3 X4 X5    
      Z       0     0 0
              0   * 1 0
              0     0 1
              1     0 0
      M -14 -1 0 0 7 -2 0 0


X2 = ( 0 , 0 , 19/20 , 0 , 0 , 127/20 , 153/20 )
min
    
Элементы строки r1 разделим на . 

      X1 X2 X3 X4 X5    
      Z       0     0 0
              0   1*   0
              0     0 1
              1     0 0
      M -14 -1 0 0 7 -2 0 0

 
Убираем искусственную  переменную r1, заменяем ее на базисную переменную X5.
Пересчитываем таблицу. 

      X1 X2 X3 X4 X5  
      Z -7 -3 0 0 24 0 0
              0   1 0
              0 * 0 1
              1   0 0
      M       0   0 0


X3 = ( 0 , 0 , 166/21 , 0  , 127/21 , 40/21 )
min
      
 

Элементы строки r2 разделим на . 

      X1 X2 X3 X4 X5  
      Z -7 -3 0 0 24 0 0
              0   1 0
              0 1* 0  
              1   0 0
      M       0   0 0

 
Убираем искусственную  переменную r2, заменяем ее на базисную переменную X4.
Все искусственные  переменные исключены, пересчитываем  таблицу симплексным методом
 
      X1 X2 X3 X4 X5
      Z       0 0 0
              0 0 1
              0 1 0
          *   1 0 0
        M 0 0 0 0 0 0

 
X4 = ( 0 , 0 , 662/57, 40/57 , 539/57 )
    
    
min
 

Разделим элементы строки X3 на 17/57
      X1 X2 X3 X4 X5
      Z       0 0 0
              0 0 1
              0 1 0
            1*     0 0

 
Пересчитываем таблицу.
      X1 X2 X3 X4 X5
      Z   0 0 3 0 0
          0     0 1
          0     1 0
            1*     0 0

 
X = ( 662/17 , 0 ,0, 70/17, 33/17)      Z = 11
  условие удовлетворено. Наибольшее значение Z=11.
Решений множество  потому, что небазисная переменная х2 в строке Z равна 0.
Ответ: max Z {662/17 ; 0 ;0; 70/17; 33/17}=11, множество решений. 
 
 
 


    Список  литературы.
 
http://www.grandars.ru/student/vysshaya-matematika/simpleksnyy-metod.html
и т.д.................


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


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.