Реализация симплекс-метода. Нахождение наименьшего значения функции

Министерство образования  Пензенской области

ГБОУ СПО ПО «Мокшанский  политехнический колледж»

 

 

 

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

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

 

Тема: «Реализация симплекс-метода. Нахождение наименьшего значения функции»

 

 

 

 

 

Выполнил студент 4 курса,

42 группы: Горшков Е.В.

Проверил преподаватель:

Трофимова О.А.

Оценка:________________

 

Мокшан 2012

Содержание

Введение 3

1. Теоретическая часть 4

1.1. Симплексный метод  решения задач линейного программирования….4

1.2. Математическое описание симплекс-метода…………………………...6

1.3 Алгоритм преобразования  коэффициентов стандартной таблицы…………………………………………………………….…………..9

2. Практическая часть 12

Заключение 18

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

 

Введение

Данная работа посвящена  изучению и реализации симплекс-метода, нахождению наименьшего значения функции.

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1. Симплексный  метод решения задач линейного  программирования

Симплекс-метод был разработан Джорджем Данцигом.

Джордж Бернард Данциг родился в Портленде, штат Орегон, США, родители дали ему среднее имя  «Бернард», в честь писателя Джорджа  Бернарда Шоу, в надежде, что он также  станет писателем. Его отец Тобиас Данциг родом из Латвии, также был математиком и учился в Париже у Анри Пуанкаре. Тобиас женился на студентке Сорбонского университета, Ане Уриссон и иммигрировал в США. В начале 1920-х годов его семья переехала в Балтимор, а впоследствии в Вашингтон, где его жена Анна Данциг стала лингвистом в Библиотеке конгресса. Джордж Данциг стал преподавать математику в Мэрилендском университете в Колледж-Парке. Джордж посещал «Powell Junior High School» и «Central High School», он был в восторге от геометрии. Его отец воспитывал в нем интерес к геометрии, часто проводя горячие дискуссии о её проблемах.

Джордж Данциг получил  степень бакалавра в области  математики и физики в Мэрилендском университете в 1936 году, степень магистра в области математики в Мичиганском университете в 1938 году. После двух лет работы в Бюро трудовой статистики Министерства труда США, он поступил на докторскую программу в области математики в Калифорнийский университет в Беркли, где изучал статистику под руководством математика Ежи Неймана. В 1939 году он опоздал на занятия и ошибочно подумал, что написанные на доске уравнения — это домашнее задание. Оно оказалось трудным, но через несколько дней он смог его решить. Оказалось, что он решил две «нерешаемые» проблемы в статистике, которые учёные не могли решить уже много лет. Эта история стала очень популярной, обросла легендами и использовалась как начало фильма «Умница Уилл Хантинг».

С началом Второй мировой  войны, Джордж взял отпуск от докторской программы в Калифорнийский университет в Беркли, чтобы работать в Учреждении статистического управления ВВС США. В 1946 году он вернулся в университет Беркли, чтобы выполнить программы университета, и получил степень доктора философии по математике в том же году.

Симплекс-метод был разработан и впервые применен для решения задач в 1947 г.  математиком Дж. Данцигом и принадлежит к числу аналитических методов решения основной задачи линейного программирования.

Симплексный метод применяется  при решении задач линейного  программирования, заданных в канонической форме. Симплексный метод основан  на том факте, что целевая функция  достигает экстремума на допустимом базисном решении. Таким образом, дело сводится к перебору базисных допустимых решений системы ограничений-равенств задачи. Симплексный метод позволяет  переходить от одного допустимого базисного  решения к другому так, чтобы  значение целевой функции уменьшалось (увеличивалось) в задаче на минимум (максимум). Все необходимые базисные решения целесообразно получить в таблице Гаусса. В первый блок таблицы заносятся данные исходной задачи. При необходимости некоторые  уравнения системы ограничений  следует умножать на —1 (чтобы все  свободные члены уравнений были неотрицательными).

Симплексный метод применяется  при решении задач линейного  программирования, заданных в канонической форме.

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

Строку, которую назовем индексной, заполняем коэффициентами целевой функции, представленной в виде уравнения

 

 

где - свободный член F(X). Вместо записываем в первом блоке только характер задачи (max или min), а в последующим блоках – результаты вычислений.

Каждая итерация, т.е. переход  от одного блока таблицы к другому  осуществляется известными элементарными  преобразованиями Гаусса-Жордана для  строк.

Если все компоненты базисного  решения положительны (мы предполагаем, что ранг системы уравнений-условий  задачи равен m, r = m), то решение называется невырожденным, в противном случае – вырожденным.

Основное содержание метода состоит в следующем:

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

1.2. Математическое описание метода.

Допустим, имеется система  уравнений ограничений:

Допустим, требуется вывести из числа свободных переменных какую  – либо переменную, например, х₂ и перевести ее в базисную, а в замен ее ввести в число свободных какую то базисную, например у₃, т. е. х₂ ↔ у₃. Если проводить этот процесс математическим способом то, необходимо было бы переразрешать каждое уравнение в системе ограничений относительно новой свободной переменной, т. е. новое получившееся уравнение, в котором была произведена замена необходимо подставить во все остальные уравнения, а так же целевую функцию. Данная процедура является громоздкой, поэтому проще задачу решить с помощью определенного алгоритма и записывать все промежуточные результаты в таблицу. Чтобы этот алгоритм был проще и лучше запоминался необходимо произвести следующие преобразования:  

  

Избавляемся от отрицательных коэффициентов, для этого принимаем

 

 

 

В	СЧ	х1	х2	х3	х4
у1	b1	a11	a12	a13	a14
у2	b2	a21	a22	a23	a24
у3	b3	a31	a32	a33	a34
у4	b4	a41	a42	a43	a44
у5	b5	a51	a52	a53	a45

При пересечении разрешающей  строки у₃ и разрешающего столбца х₂ получаем разрешающий элемент а_32.

Необходимо найти коэффициенты, которые получатся в разрешающей  строке после обмена х₂ ↔ у_3.

	СЧ	х1	у3	х3	х4
у1
y2
x2
y4
y5

 

1.3 Алгоритм преобразования  коэффициентов стандартной таблицы.

1. Разрешающий элемент заменяется на обратную ему величину.
2. Все остальные элементы разрешающей строки делятся на разрешающий элемент.
3. Все элементы разрешающего столбца, кроме самого разрешающего элемента делятся на разрешающий элемент и меняют знак.
4. Каждый из остальных элементов подвергаются следующему преобразованию: к нему прибавляются произведение элементов, стоявшего в прежней разрешающей строке на том же месте по порядку (т. е. в том же столбце), на элемент стоящий в новом разрешающем столбце на соответствующем месте (т. е. в той же строке, что и рассчитываемый элемент).

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

Алгоритм преобразования x_j ↔ y_i стандартной таблицы сводится к следующим операциям:

1. Выделить в таблице разрешающий элемент. Вычислить ее обратную величину и записать в нижней части этой же ячейки, например в правом нижнем углу.
2. Все элементы разрешающей строки, кроме самого разрешающего элемента умножить на , результат записать в нижней части той же ячейки.
3. Все элементы разрешающего столбца, кроме всего разрешающего элемента умножить на на – a, записать в нижней части той же ячейки.
4. Подчеркнуть в разрешающей строке все верхние числа (прежние элементы) за исключением самого разрешающего элемента. А в разрешающем столбце все новые элементы, кроме самого разрешающего элемента.
5. Для каждого из элементов не принадлежащих ни к разрешающей строке, ни к разрешающему столбцу в нижней часть ячейки записать произведение выделенных чисел, стоящих в той же строке и в том же столбце, что и данный элемент.
6. Переписать таблицу, заменив:
• x_j на  y_i;
• элемент разрешающей строки и столбца, числами, стоящими в нижней части тех же ячеек;
• каждый из остальных элементов суммой чисел стоящей в верхней и нижней части той же ячейки.

В любой задаче ОЗЛП существует так  же линейная функция L, которая в общем случае выглядит следующим образом:

Для решения ее табличным способом ее так же можно привести к стандартному виду.

Таким образом, в стандартной таблице  появляется еще одна строка L. С ней производятся только такие же вычисления как со всеми остальными ячейками таблицы, строка L никогда не может быть разрешающей строкой. С помощью табличного алгоритма обмена переменных в управлениях ОЗЛП можно решить любую задачу линейного программирования или убедиться, что она не имеет решения.

Нахождение решения каждой задачи распадается на два этапа:

1. нахождение опорного плана;
2. отыскание оптимального решения.

В процессе первого этапа выясняется, имеет ли данная задача допустимые не отрицательные решения, если да, то находиться опорное решение, для  которого все остальные переменные равны 0, а все базисные не отрицательные.

В процессе второго этапа выясняется, ограничена ли снизу функция L, которая стремиться к минимуму, если нет, то оптимального решения не существует. Если да, то оно отыскивается после замены x на y.