Курсовая работа - Симплекс метод линейного программирования - файл n1.doc

Курсовая работа - Симплекс метод линейного программирования
скачать (50.5 kb.)
Доступные файлы (1):
n1.doc51kb.26.08.2012 15:19скачать

n1.doc





Содержание:

Введение

1.Обыкновенные и модифицированные жордановы исключения

2.Решение неоднородных систем методом Жордана – Гаусса

3.Идея симплекс метода

4.Построение начального опорного решения

5.Критерии оптимальности

5.1.Признак оптимальности опорного плана

5.2. Возможность переход от одного опорного плана к другому

5.3.Признак неограниченности целевой функции на множестве планов

5.4.Признак бесконечности множества оптимальных планов

Заключение

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

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

1.Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа  2Х+ 5Х ? 10,       то, очевидно,  0 ? Х? 10/2 = 5 и 0 ? Х? 10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.

Проведем перебор точек параллелепипеда с шагом 1/10n  последовательно при  n=2,3,…, вычисляя значения целевой функции и проверяя наличие ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено!

2.Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)

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

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

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

f(x1,x2,…,xn)=c1x1+c2x2+…+cnxn? max (min) (1)

(2)

(3)


Выделяют две формы задач линейного программирования:

1.стандартная форма


2.каноническая форма
Планом называется вектор x=(x1,x2,…,xn) Rn , удовлетворяющий условиям (1)-(3). Множество всех допустимых решений задачи будем обозначать через X .допустимое решение x X, при котором целевая функция (1) достигает наибольшего (max) или наименьшего значения (min), называется оптимальным решением задачи линейного программирования. Базисное неотрицательное решение x=(x1,x2,…,xr,0,…,0) , где r- ранг системы ограничений (2), называется опорным решением (2) .


1.Обыкновенные и модифицированные жордановы исключения

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

Пусть дана система из m линейных функций y1,…,ym от n неизвестных x1,x2,…,xn : yi=? aij xj (1.1), где aij – постоянные величины( i =1,m; j =1,n).

Представим систему (1.1) в форме таблицы 1.3,


Таблица 1.3.




x1 … xj … xs … xn

y1=



yi=



yj=



ym=

a11 … a1j … a1s … a1n

………………………………….

ai1 … aij … ais … ain

…………………………………

ak1 … akj … aks … akn

…………………………………

am1 … amj … ams … amn



которую в дальнейшем будем называть жордановой. Перейдём к обычной записи системы путём умножения элементов aij i-й строки на соответствующие неизвестные xj , стоящие в верхней


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

1.Ашманов С.А., Линейное программирование. М.: Наука 1981.

2.Кузнецов А.В., Холод Н.И., Математическое программирование. Мн.: Высшая школа 1984

3.Кузнецов А.В., Холод Н.И., Костевич Л.С., Руководство к решению задач по математическому программированию. Мн.: 2001

4.Кузнецов А.В., Холод Н.И., Новикова Т.И. сборник задач по математическому программированию. Мн.: Высшая школа 1994

5.Кузнецов А.В., Холод Н.И., Сокович В.А.., Высшая математика. Математическое программирование. Мн.: Высшая школа 1987

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации