Линейное програннирование

Федеральное агентство железнодорожного транспорта

Сибирский государственный  университет путей  сообщения 
 
 
 

Кафедра «Бухгалтерский учет и аудит на железнодорожном транспорте» 
 
 

Курсовая  работа 

по дисциплине: «Математическое программирование» 
 
 
 

Руководитель:                                                                           Разработал:

                                                                                                    студент ЗФ  09-ВЭ-59 

___________   Баранова  Н.В.                                              __________ Маликов Р.Ф.

      ^{(подпись)                                                                                     (подпись)}

______________                                                           _____________

  ^{(дата проверки)                                                                   (дата сдачи на проверку)} 
 
 
 

Краткая рецензия

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

_____________________

    ^{(запись о доступе к защите)}

______________________                                                         ______________________

  ^{(оценка по результатам защиты)                                                                                           (подпись преподавателя)} 
 
 

Новосибирск 2011 
 

Задача  № 1

Дана задача линейного программирования:

Требуется:

1. Решить исходную задачу графическим способом.
2. Построить симметричную двойственную задачу и решить ее аналитическим способом.
3. Используя теоремы двойственности, найти оптимальные оценки исходной задачи.

Решение.

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

Построим  в системе координат Oх₁х₂ прямые, соответствующие неравенствам системы:

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

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

 
 
 
 
 

  
 
 
 
 
 
 
 
 
 

Координаты точки  В найдем из системы двух уравнений прямых, пересечением которых точка В является:

          

Найдем  значения целевой функции в каждой вершине построенного многоугольника: 

 

Отсюда видно, что целевая функция Z= достигает своего минимального значения -14 в точке В(2,3).

 Таким образом,  задача имеет решение  . 

2. Преобразуем систему

 в систему   

Каждому ограничению в исходной задаче должно соответствовать неизвестное в двойственной задаче:

 

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

 

Получим систему  ограничений для двойственной задачи:

 

 

Решим симметричную двойственную задачу аналитическим  способом.

Найдем  наибольшее значение линейной функции при следующих ограничениях:

Получим

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

     К левой части неравенства 1 системы  ограничений прибавляем неотрицательную  переменную y₄, тем самым мы преобразуем неравенство 1 в равенство. От левой части неравенства 2 системы ограничений отнимаем неотрицательную переменную y₅, тем самым мы преобразуем неравенство 2 в равенство.

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

     Определимся с начальным опорным решением.

     Переменная  y₄ входит в уравнение 1 с коэффициентом 1, а в уравнение 2 системы с коэффициентом ноль, т.е. y₄ - базисная переменная.

     В уравнении 2 нет переменной, которая  входила бы в него с коэффициентом 1, а в остальные уравнения системы  входила бы с коэффициентом ноль. Добавим к данному уравнению искусственную переменную y₆. Очевидно, переменная y₆ будет являться базисной переменной, т.к. входит в уравнение 2 с коэффициентом 1 и не входит в уравнение 1 системы ограничений.

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

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

     Из  уравнения 2 последней системы выразим  y₆ и подставим в выражение функции W:

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

     Для составления начальной симплекс таблицы выполнены все условия.

При составлении  исходной симплекс таблицы, коэффициенты при переменных функции Z*(y) записываются с противоположными знаками, а свободный член со своим знаком.

Для функции W правило такое же.

     За  ведущий выберем столбец 2, так  как -2 - наименьший элемент в строке W (если есть несколько одинаковых наименьших, то выбираем любой). Элемент строки W, принадлежащий столбцу свободных членов, не рассматриваем.

За ведущую  выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для строки 1 является наименьшим. Отношение вычисляем только для положительных элементов столбца 2. 

 

     От  элементов строки 2 отнимаем соответствующие элементы строки 1, умноженные на -2. От элементов строки Z*(y) отнимаем соответствующие элементы строки 1, умноженные на -5. От элементов строки W отнимаем соответствующие элементы строки 1, умноженные на -2. Базисной является теперь переменная y₂. Элементы столбца y₆ можно не пересчитывать, так как переменная y₆ больше не является базисной. 

 

     За  ведущий выберем столбец 3, так как -4 - наименьший элемент в строке W.

За ведущую  выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для строки 2 является наименьшим. Отношение вычисляется только для положительных элементов столбца 3. 

 

     Все элементы строки W симплекс таблицы равны нулю. Мы исключили из базиса искусственные переменные. Нашли начальное решение для рассматриваемой функции при заданных ограничениях. Строка W нам больше не нужна.