Симплексный метод

Размещено на http://www.allbest.ru/

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКОЙ ОБЛАСТИ

Международный университет природы, общества и человека « Дубна »

Кафедра Информационные технологии

КОНТРОЛЬНАЯ РАБОТА

Теория принятия решений

ТЕМА: «Симплексный метод»

Выполнил: Сакулина Кристина

Руководитель: Гусев В.В.



Содержание

Введение

1. Общая характеристика симплексного метода

2. Алгоритм решения задач линейного программирования симплекс-методом

3. Примеры решения задач симплекс-методом

4. Компьютерная реализация симплекс-метода при решении задач линейного программирования

Заключение

Список использованной литературы



Введение

Работа посвящена наиболее распространенному методу решения задачи линейного программирования (симплекс-методу). Симплекс-метод является классическим и наиболее проработанным методом в линейном программировании. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует.

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

Дисциплины, в которых изучаются модели и методы оптимизации («Методы оптимизации и теория принятия решений», «Исследование операций», Математические модели исследования экономики и математическое программирование») присутствуют во многих образовательных программах профессионального образования. Как правило, это программы по направлениям инженерного образования.

Это очевидно объясняется тем, что современное управление, требующее принятия решений, имеющих не только большое стоимостное выражение, но и различные социальные последствия, должно быть обеспечено разнообразным инструментарием, позволяющим осуществлять выбор из имеющихся вариантов, если не наилучшего (оптимального) решения, то, во всяком случае, предпочтительного с точки зрения лица принимающего решение. Необходимость изучения методов оптимизации и теории принятия решений в инженерных направлениях и специальностях обусловлена, как минимум, двумя факторами. Во-первых, большинство инженеров рано или поздно становятся руководителями (линейными, среднего или высшего звена) и, следовательно, вынуждены принимать управленческие решения, во-вторых, сама инженерная деятельность предполагает принятие многочисленных технических и технологических решений (при проектировании наилучшей конструкции двигателя, в случае выбора оптимальной последовательности обработки потоков задач и оптимального режима функционирования энергостанций и во многих других ситуациях). Сегодня оптимизационные задачи и задачи принятия решений моделируются и решаются в самых различных областях техники.

Очевидно, что логика современных инновационных программ инженерного образования, включающих в себя блок курсов, связанных с эффективным управлением (стратегический и операционный производственный менеджмент, управление проектами, инновационный менеджмент и др.), и сопровождаемых технологиями проблемного и проектного обучения, предполагает, что обучающиеся должны владеть навыками математического обоснования принятия решений. К ним относятся и навыки математического моделирования оптимизационных задач, выбора адекватного математического обеспечения (метода, алгоритма, программной системы) с необходимым обоснованием, анализа полученных результатов и их интерпретации в терминах предметной области.

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

В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это, так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства («Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о диете», «Транспортная задача» и т.д.). Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

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

В основу симплексного метода положена идея последовательного улучшения получаемого решения.

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

Таким образом, имея систему ограничений, приведенную к канонической форме (все функциональные ограничения имеют вид равенств), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому, обязательно допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении целевая функция, если и не достигнет оптимума, то приблизится к нему (или, по крайней мере, не удалится от него). С новым допустимым базисным решением поступают так же, пока не отыщется решение, которое является оптимальным.

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1) способ определения какого-либо первоначального допустимого базисного решения задачи;

2) правило перехода к лучшему (точнее, не худшему) решению;

3) критерий проверки оптимальности найденного решения.

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

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



1. Общая характеристика симплекс-метода

В общем виде, когда в задаче линейного программирования участвуют N-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более 3, весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.

Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение целевой функции при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение целевой функции. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима. [5]

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные х1, х2, ..., хr. Переменные x1, x2,…, xr называются базисными, а весь набор {x1, x2,…, xr} - базисом, остальные переменные называются свободными, система ограничений (1) называется системой, приведенной к единичному базису.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения и являются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные х1, х2, ..., хr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ? 0.

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение f самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции f не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям. Его идея состоит в следующем.

Имея систему ограничений, приведенную к общему виду, то есть к системе m линейных уравнений с n переменными (m < n), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще.

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

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

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

Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения. При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Но так как число базисных решений всегда ограниченно, то ограниченно и число шагов симплексного метода. Если ограничительные условия заданы неравенствами, то их можно преобразовать в равенства путем введения новых неотрицательных переменных - так называемых балансовых (выравнивающих). Так, например, в неравенствеa1x1+ a2x2+…+ anxn ? b достаточно добавить в левую часть некоторую величину xn+1 ? 0 и получится равенство a1x1+ a2x2+…+ anxn+ xn+1=b.

Если переменная xl не подчинена условию неотрицательности, то её заменяют разностью двух неотрицательных переменных: xl = ul- vl, где ul, vl ? 0.

Задача минимизации функции f может быть сведена к задаче максимизации функции f.

Основные теоретические положения симплексного метода

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

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

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит :

- умение находить начальный опорный план;

- наличие признака оптимальности опорного плана;

-умение переходить к не худшему опорному плану.



2. Алгоритм решения задач линейного программирования симплекс-методом

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

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

· Привести задачу к каноническому виду.

· Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости Привести системы ограничений).

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

· Если выполняется признак единственности оптимального решения, то решение задачи заканчивается.

· Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.

Для того чтобы задача имела оптимальное решение необходимо:

- чтобы ограничения задачи были совместимы;

- целевая функция была ограничена сверху при поиске максимального значения и снизу при поиске минимального значения.

- ограничения вида «меньше или равно» приводятся к строгому равенству путём добавления к левой части каждого ограничения неотрицательной целой переменной, которая записывается в целевую функцию с коэффициентом равным нулю;

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

Если в базисе остались искусственные переменные, то задача решений не имеет;

Если среди относительных оценок есть отрицательные, то данный план не оптимален и необходим переход к следующему базисному плану.

3. Примеры решения задач симплексным методом

Решить симплексным методом задачу: Симплексный метод

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x6 с коэффициентом +1. В целевую функцию переменная x6 входит с коэффициентом ноль (т. е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6). Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Дk = CбXk -- ck

Где:

· Cб = (с1, с2, ... , сm ) -- вектор коэффициентов целевой функции при базисных переменных

· Xk = (x1k, x2k, ... , xmk ) -- вектор разложения соответствующего вектора Ак по базису опорного решения

· Ск -- коэффициент целевой функции при переменной хк.

Оценки векторов входящих в базис всегда равны нулю. Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу :

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

В последней строке таблицы с оценками Дk в столбце "А0" записываются значения целевой функции на опорном решении Z(X1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Д1 = -2, Д3= -9 для векторов А1 и А3 отрицательные.

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

Вычисляем значения параметра и01 для первого и третьего столбцов.

Получаем и01 = 6 при l = 1, и03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора ДZ1 = -- 6*(- 2) = 12, и третьего вектора ДZ3 = -- 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра и03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5).

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Д2 = -- 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр и02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Д1 = 7/2, Д4 = 2, Д6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

Рассмотрим еще одну задачу:

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

-5x1-x2+2x3?2;

-x1+x3+x4?5; (2.5)

-3x1+5x4?7.

Требуется минимизировать линейную функцию Z=5x1-2x3

Приводя неравенства к стандартному виду (?0) и вводя добавочные переменные y1, y2, y3 переходим к условиям-равенствам:

y 1 =5x 1 +x 2 -2x 3 +2

y 2 =x 1 -x 3 -x 4 +5

y 3 =3x 1 -5x 4 +7

Число переменных (n = 7) на 4 превышает число уравнений (т = 3). Значит, четыре переменные могут быть выбраны в качестве свободных. Пусть в качестве свободных переменных выступают x1, x2, x3, x4. Положим их равными нулю и получим опорное решение:

x1=x2=x3=x4=0;

y1=2, y2=5, y3=7.

При этих значениях переменных Z= 0.

Это решение не оптимально, поскольку в линейной функции Z коэффициент при x3 отрицателен. Значит, увеличивая x3 можно уменьшить Z.

Попробуем увеличивать x3. Из выражений видно, что в y1 и y2 переменная x3 входит с отрицательным коэффициентом, значит, при увеличении x3 соответствующие переменные могут стать отрицательными.

Определим, какая из этих переменных (y1 или y2) раньше обратится в нуль при увеличении x3. Очевидно, что это y1 она станет равной нулю при x3=1, а величина y2-- только при x3= 5.

Выбирается переменная у, и вводится в число свободных вместо x3. Чтобы разрешить систему относительно x3, y2, y3поступим следующим образом. Разрешим первое уравнение относительно новой базисной переменной x3:

x3=5/2*x1+1/2*x2-1/2*y1+1

Это выражение подставляется вместо x3 во второе уравнение:

x 3 =5/2*x 1 +1/2*x 2 -1/2y 1 +1;

y 2 =-3/2*x 1 -1/2*x 2 +1/2*y 1 -x 4 +4;

y 3 =3x 1 -5x 4 +7.

Что касается третьего уравнения, то оно, как не содержащее x3 не изменится. Система приведена к виду со свободными переменнымиx1, x2, y1, x4и базисными x3, y2, y3.

Положим теперь свободные переменные равными нулю. Функция приобретает значение Z=-2, что меньше (лучше), чем прежнее значение Z= 0.

Это решение все еще не оптимально, так как коэффициент при x2 в выражении отрицателен, и переменная x2 может быть увеличена. Это увеличение, как это видно из системы, может сделать отрицательной y2 (в первое уравнение x2 входит с положительным коэффициентом, а в третьем -- отсутствует).

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

x3=x1-y2-x4+5

y2=-3x1-2y2+y1-2x4+8

y3=3x1-5x4+7

Выразим Z через новые свободные переменные:

Z=3x1+2y2-y1+2x4-8+y1-2=3x1+2y2+2x4-10

Полагая x1=y1=y2=x4=0 , получим Z = -10.

Это решение является оптимальным, так как коэффициенты при всех свободных переменных в выражении неотрицательны. Итак, оптимальное решение ОЗ найдено:

x1*=0, x2*=8, x3*=5, x4*=0, y1*=0, y2*=0, y3*=7.

При таких значениях переменных линейная функция Z принимает минимальное значение: Zmin=-10

Заметим, что в рассмотренном примере нам не пришлось искать опорное решение: оно сразу же получилось, когда мы положили свободные переменные равными нулю. Это объясняется тем, что в уравнениях (2.5) все свободные члены были неотрицательны и, значит, первое же попавшееся решение оказалось опорным. Если это окажется не так, можно будет прийти к опорному решению с помощью такой же процедуры обмена местами некоторых базисных и свободных переменных, повторно решая уравнения до тех пор, пока свободные члены не станут неотрицательными.



4. Компьютерная реализация симплекс-метода при решении задач линейного программирования

симплекс линейный программирование неравенство

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

* порождение начального базисного допустимого решения;

* поиск оптимального плана и экстремума нецелочисленной задачи линейного программирования;

* поиск оптимального плана и экстремума полностью целочисленной задачи линейного программирования;

* поиск оптимального плана и экстремума частично целочисленной задачи линейного программирования;

При проектировании был использован принцип модульного программирования, что упрощает отладку программы и позволяет расширять ее функциональные возможности. Алгоритмическая часть программы имеет модульно-иерархическую структуру, в которой каждый модуль является самостоятельной частью программы и взаимодействует с другими модулями в порядке, установленном разработчиками. Методы решения задач линейной оптимизации, реализованные в программно-алгоритмическом комплексе, основаны на построении симплекс-таблиц, поэтому в структуре программы все алгоритмические модули связаны с модулем, организующим решение задачи линейного программирования симплекс-методом. Входными данными для этого модуля является целевая функция с указанием типа экстремума (максимум или минимум) и ограничения, накладываемые на управляемые переменные. Ограничения задаются в виде уравнений или неравенств. Далее управление передается второму модулю, где формируется начальное допустимое базисное решение. Второй, третий и четвертый модули на каждой итерации реализуемого метода вызывают модуль построения симплекс-таблиц, которому они передают текущий результат. Связь между модулями организована через внешние структуры данных. Так, например, для задания линейного критерия оптимальности, вектора управляемых переменных, вектора ограничений и матрицы ограничений используются одномерные и двумерные статические массивы, а симплекс-таблица в памяти ЭВМ представлена как двумерный динамический массив, способный изменять свою размерность, удаляя или добавляя строки и столбцы к симплекс-таблице. Рассмотрим особенность функционирования программного комплекса. Для организации диалога с пользователем применяется стандартный графический интерфейс Windows, построенный на основе библиотеки визуальных компонентов VCL (VisualComponentLibrary), поставляемой вместе с пакетом Delphi. При разработке программы использовалась MDI-технология (MultipleDocumentInterface - многодокументный пользовательский интерфейс), что позволяет пользователю работать сразу с несколькими задачами линейного программирования. В программе реализована активная форма диалога, позволяющая выбирать режимы: расчет, просмотр и редактирование информации, получение справки и т.д. Главное меню содержит следующие пункты: файл, правка, вид, вычисления, окно, справка. Все пункты главного меню вызывают подменю. В начале работы программы некоторые пункты запрещены и становятся разрешенными только по мере выбора других пунктов меню (например, меню «Правка», «Вычисления» и т. д.).

В программе предусмотрена возможность настройки параметров задачи: максимизация или минимизация; выбор опции, позволяющей просматривать промежуточные результаты итераций; ограничения количества итераций; установка размерности задачи т. п.



Заключение

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

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

Задачи линейного программирования решаются несколькими методами: 1. графический метод;

2. симплекс-метод;

3. двойственный симплекс-метод.

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

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



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

Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов / И. Л. Акулич. - М.: Высшая школа, 1986.

Гончаров Е. Н. Исследование операций. Примеры и задачи: учебное пособие / Е. Н. Гончаров, А. И. Ерзин, В. В. Залюбовский. -Н.: Гос. ун-т. Новосибирск, 2005.

Павлова Т. Н. Линейное программирование: учебное пособие / Т. Н. Павлова, О. А. Ракова. - Д.: 2002.Карманов В.Г. Математическое программирование: учебное пособие для студентов вузов. - М.: Физматлит, 2001. - 264с.

Кузнецов А.В. Математическое программирование: учебное пособие для вузов. - М.: Высшая школа, 1976. - 352с.

Жиглявский А.А., Жилинкас А.Г. Методы поиска глобального экстремума. -- М.: Наука, Физматлит, 1991.

Сайт http://ru.wikipedia.org/wiki

Сайт http://fessagicadif.web44.net

Размещено на Allbest.ru