Задача

Задача Линейное програннирование

Работа добавлена на сайт bukvasha.net: 2015-10-29

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 20.2.2025





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

Сибирский государственный университет путей сообщения
Кафедра «Бухгалтерский учет и аудит на железнодорожном транспорте»
Курсовая работа
по дисциплине: «Математическое программирование»
Руководитель:                                                                           Разработал:

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

­­­­­­­

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

      (подпись)                                                                                     (подпись)

______________                                                           _____________

  (дата проверки)                                                                   (дата сдачи на проверку)
Краткая рецензия

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

_____________________

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

______________________                                                         ______________________

 (оценка по результатам защиты)                                                                                           (подпись преподавателя)
Новосибирск 2011





Задача № 1

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







Требуется:

1.     Решить исходную задачу графическим способом.

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

3.     Используя теоремы двойственности, найти оптимальные оценки исходной задачи.

Решение.

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

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



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

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





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

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







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

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

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





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

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

 


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

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



Получим



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

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



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

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

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

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



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



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



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



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

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

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

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

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

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



базисные
переменные


y1

y2

y3

y4

y5

y6

свободные
члены


отношение

y4

1

1

-1

1

0

0

2

2/1=2

y6

-1

2

2

0

-1

1

6

6/2=3

Z*(y)

-3

-5

0

0

0

0

0



W

1

-2

-2

0

1

0

-6





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



базисные
переменные


y1

y2

y3

y4

y5

свободные
члены


отношение

y2

1

1

-1

1

0

2



y6

-3

0

4

-2

-1

2

2/4=0.5

Z*(y)

2

0

-5

5

0

10



W

3

0

-4

2

1

-2





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

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



базисные
переменные


y1

y2

y3

y4

y5

свободные
члены


отношение

y2

1

4

0

2

-1

10



y3

-3

0

4

-2

-1

2



Z*(y)

-7

0

0

10

-5

50



W

0

0

0

0

0

0





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



базисные
переменные


y1

y2

y3

y4

y5

свободные
члены


отношение

y2

1

4

0

2

-1

10

10/1=10

y3

-3

0

4

-2

-1

2



Z*(y)

-7

0

0

10

-5

50





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

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

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



базисные
переменные


y1

y2

y3

y4

y5

свободные
члены


отношение

y1

1

4

0

2

-1

10



y3

0

12

4

4

-4

32



Z*(y)

0

28

0

24

-12

120





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

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

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




Задача № 2

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







Требуется:

1.     Решить задачу графическим способом.

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

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



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

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





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

                               

           

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

.

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




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

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



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










Имеем:










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







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

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





Отсюда, при x1=5, x2=5, =0 получим:

16-10--3=0

8-10-+5=0.

Отсюда

=3 ≥ 0

=1 ≥ 0.

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

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

1. Реферат на тему Existence Of God Essay Research Paper Philosophy
2. Реферат Повна характеристика Житомирської області
3. Лекция на тему Предмет методы и задачи социально экономической статистики
4. Реферат на тему Psychology In Sports Essay Research Paper The
5. Биография на тему Давид Бергельсон
6. Курсовая Менеджмент в социально-культурном сервисе и туризме
7. Реферат Вторжение космических тел в атмосферу Земли
8. Реферат на тему Эволюция и естественный отбор
9. Реферат на тему Why Does Socrates Claim That No Person
10. Реферат на тему Sports Essay Research Paper For this assignment