Линейное программирование - Курсовая работа

В зависимости от свойств функций f и g, математическое программирование можно рассматривать как ряд самостоятельных дисциплин, занимающихся изучением и разработкой методов решения определенных классов задач. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве. В результате решения таких задач требуется в общем случае найти максимум (или минимум) квадратичной функции при условии, что ее переменные удовлетворяют некоторой системе линейных неравенств или линейных уравнений либо некоторой системе, содержащей как линейные неравенства, так и линейные уравнения. В задачах дробно-линейного программирования целевая функция представляет собой отношение двух линейных функций, а функции, определяющие область возможных изменений переменных, также являются линейными. Если в целевой функции или в функциях, определяют область возможных изменений переменных, содержатся случайные величины, то такая задача относится к задаче стохастического программирования.Чтобы определить искомую полуплоскость нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей и проверить: удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка. Для этого, построив прямую (I) x1-x2 =-3, возьмем какую-нибудь точку, принадлежащую одной из двух полученных полуплоскостей, например, точку O(0,0). Координаты этой точки удовлетворяют неравенству x1-x2 ?-3. Значит полуплоскость, которой принадлежит точка O(0,0) определяется неравенством x1-x2 ?-3.Симплекс-метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным). Идея метода состоит в последовательном продвижении по базисам опорных планов задачи, т.е. в последовательном улучшении планов задачи по определенному критерию, до тех пор, пока не будет получено оптимальное решение. ввести в исходную симплекс-таблицу следующие параметры, соответствующие начальному базисному решению: весовые коэффициенты при переменных в целевой функции (строка ); переменные, которые входят в текущий базис (столбец ); значения базисных переменных - = (столбец ); элементы ¦aij¦, i=1,…,m, j=1,…,n, матрицы условий задачи (А1, А2,…, An); оценки , ?j, j=1,…,n, соответствующие векторам А1, А2,…, An (последняя индексная строка). 2) число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего вектору, вводимому в базис; 3) число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и строки вновь вводимого в базис вектора (как отмечено выше, эта строка получается из строки исходной симплекс-таблицы делением ее элементов на разрешающий элемент).Если в таблице полученные коэффициенты небазисных переменных в строке ?j - отрицательные, то данное решение не оптимальное и нужно переходить к следующей итерации. Вводимая переменная определяется среди множества небазисных переменных, как переменная, имеющая наибольший отрицательный коэффициент в ?j-строке. Для этого: - вычислим элементы новой направляющей строки , согласно: новая направляющая строка, = текущая направляющая строка / направляющий элемент -вычислим элементы остальных строк, согласно: новая строка = текущая строка - ее коэффициент в направляющем столбце * новая направляющая строка. Так как во второй таблице в строке ?j имеются отрицательные числа, то продолжаем делать вычисления до тех пор, пока в строке ?j все числа не будут положительными.Назначение данной программы состоит в определении наименьшего или наибольшего значения целевой функции.Программа состоит из файла с расширением *.m. Задаем условие на цикл. Пока параметр p больше нуля, программа будет выполняться. Задание интервала в графической таблице по оси x1, в данном случае интервал задается от 0 до 10. Так как x1-x2 ?-3, заменяя неравенство равенством, получаем x1-x2 =-3.Processor Intel Pentium 4 3000 MHZ, RAM 512 MB, Video NVIDIA GEFORCE FX 5200, HDD 80 GB, OS Windows XP Professional, клавиатура, мышь.Записывается код программы в текстовый редактор (если программа существует, то выбрать каталог, в котором находится сохраненный файл).Входными данными служат система ограничений целевой функции, а выходными данными является график, min функции. Файл не найден Файл не находится в текущем каталоге Выбрать каталог, где находится файлВ ходе выполнения курсовой работы, было найдено решение исходной задачи линейного программирования двумя способами: графическим методом и табличным симплекс-методом.

Содержание

ВВЕДЕНИЕ

1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЛП)

2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛП

3. ТАБЛИЧНЫЙ СИМПЛЕКС-МЕТОД

4. РЕШЕНИЕ ПОСТАВЛЕННОЙ ЗАДАЧИ СИМПЛЕКСНЫМ МЕТОДОМ

5. ОПИСАНИЕ ПРОГРАММЫ

5.1 Функциональное назначение

5.2 Описание логической структуры

5.3 Используемые технические средства

5.4 Вызов и загрузка

5.5 Входные и выходные данные

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

В ходе выполнения курсовой работы, было найдено решение исходной задачи линейного программирования двумя способами: графическим методом и табличным симплекс-методом. В графической части представлен график, показывающий решение данной задачи. Также было разработано приложение для решения исходной задачи ЛП графическим методом. Результаты решений задачи линейного программирования совпадают. Максимум функции равен 4.

1. Акулич И.Л. «Математическое программирование в примерах и задачах»: Учеб. Пособие для студентов эконом. спец. вузов. - М.: Высш. шк., 1986. - 319 с., ил.

2. Зайченко Ю.П., Шумилова С.А. «Исследование операций». Сборник задач. - 2-е изд., перераб. и доп. - К. «Высшая школа». 1990. - 239 с. : ил.

3. Тах Х.А. «Введение в исследование операций» 7-е издание.: Пер. с англ. - М.: Издательский дом "Вильяме", 2005. - 912 с: ил. - Парал. тит. англ.