Задача Линейное програннирование
Работа добавлена на сайт bukvasha.net: 2015-10-29Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Федеральное агентство железнодорожного транспорта
Сибирский государственный университет путей сообщения
Кафедра «Бухгалтерский учет и аудит на железнодорожном транспорте»
Курсовая работа
по дисциплине: «Математическое программирование»
Руководитель: Разработал:
студент ЗФ 09-ВЭ-59
___________ Баранова Н.В. __________ Маликов Р.Ф.
(подпись) (подпись)
______________ _____________
(дата проверки) (дата сдачи на проверку)
Краткая рецензия
________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
_____________________
(запись о доступе к защите)
______________________ ______________________
(оценка по результатам защиты) (подпись преподавателя)
Новосибирск 2011
Задача № 1
Дана задача линейного программирования:
Требуется:
1. Решить исходную задачу графическим способом.
2. Построить симметричную двойственную задачу и решить ее аналитическим способом.
3. Используя теоремы двойственности, найти оптимальные оценки исходной задачи.
Решение.
1. Решить исходную задачу графическим способом возможно, т.к. в ней используются две переменные.
Построим в системе координат Oх1х2 прямые, соответствующие неравенствам системы:
Согласно знакам неравенств системы выделим соответствующие полуплоскости и найдем область допустимых решений задачи как пересечение получившихся полуплоскостей. Получили многоугольник ABCD – множество допустимых решений.
Целевая функция Z=
Координаты точки В найдем из системы двух уравнений прямых, пересечением которых точка В является:
Найдем значения целевой функции в каждой вершине построенного многоугольника:
Отсюда видно, что целевая функция Z=
Таким образом, задача имеет решение
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 окружности разных радиусов, видим, что минимальное значение целевая функция принимает в точке С, в которой окружность касается области решений. Для определения координат этой точки составим систему двух уравнений (2) и (3), точкой пересечения графиков которых точка С является:
Таким образом,
2. Имеем условия Куна-Таккера в дифференциальной форме:
Покажем, что существует Λ(0)≥0, при котором в точке оптимума выполняются условия Куна-Таккера для функции Лагранжа F(X,Λ).
Составим функцию Лагранжа исходной задачи:
Находим частные производные:
Имеем:
Подставляя найденное решение x1=5, x2=5 в последние три уравнения, получим:
Отсюда видим, что переменная
Так как x1=5, x2=5 – не равны нулю, то из первых двух уравнений имеем:
Отсюда, при x1=5, x2=5,
16-10-
8-10-
Отсюда
Следовательно, в точке (X(0), Λ(0)) выполняются условия Куна-Таккера и она действительно является точкой экстремума и седловой точкой функции Лагранжа.
Список литературы:
1. Кузнецов Ю.Н. «Математическое программирование: учебное пособие для экономических специалностей вузов», М., 1980г.
