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

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

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

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

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

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

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

                                                                                                    студент ЗФ  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 нам больше не нужна. 

     За  ведущий выберем столбец 1, так как -7 - наименьший элемент в строке Z*(y).

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

От элементов строки 2 отнимем соответствующие элементы строки 1, умноженные на -3. От элементов строки 3 отнимем соответствующие элементы строки 1, умноженные на -7.  

     За  ведущий выберем столбец 5, так  как -12 – наименьший элемент в  строке Z*(y). В разрешающем столбце все элементы отрицательные, поэтому решение данной задачи симплекс методом бесконечно. 
 

3. Согласно первой теореме двойственности, необходимо выполнение условия Z(x)= Z*(y).

Найдем с помощью  надстройки «Поиск решения» в электронной  таблице Excel решение исходной задачи. 

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

Задача  № 2

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

Требуется:

1. Решить задачу графическим способом.
2. Используя условия Куна-Таккера, доказать, что найденная точка является седловой для функции Лагранжа.

Решение.

1. Построим в системе координат Ox₁x₂ прямые, соответствующие неравенствам системы:

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

    Полагая значение целевой функции Z равным некоторому числу h, получаем линии уровня, а именно окружности с центром E(8, 4) и радиусом . С увеличением (уменьшением) числа h значения функции Z соответственно увеличиваются (уменьшаются).

    Проводя из точки E окружности разных радиусов, видим, что минимальное значение целевая функция принимает в точке С, в которой окружность касается области решений. Для определения координат этой точки составим систему двух уравнений (2) и (3), точкой пересечения графиков которых точка С является:

    Таким образом,

.

2. Имеем условия Куна-Таккера в дифференциальной форме:

    Покажем, что существует Λ⁽⁰⁾≥0, при котором в точке оптимума выполняются условия Куна-Таккера для функции Лагранжа F(X,Λ).

    Составим  функцию Лагранжа исходной задачи:

Находим частные  производные:

Имеем:

Подставляя найденное  решение x₁=5, x₂=5 в последние три уравнения, получим:

Отсюда видим, что переменная должна принимать нулевое значение, а и могут принимать ненулевые значения.

Так как x₁=5, x₂=5 – не равны нулю, то из первых двух уравнений имеем:

Отсюда, при x₁=5, x₂=5, =0 получим:

16-10- -3 =0

8-10- +5 =0.

Отсюда

=3 ≥ 0

=1 ≥ 0.

Следовательно, в точке (X⁽⁰⁾, Λ⁽⁰⁾) выполняются условия Куна-Таккера и она действительно является точкой экстремума и седловой точкой функции Лагранжа. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Список литературы:

1. Кузнецов Ю.Н. «Математическое программирование: учебное пособие для экономических специалностей вузов», М., 1980г.