Симплекс – метод

2.2.1. Симплекс – метод

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1, ..., Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1, ..., Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1:

X₀ + A_0,m+1*X_m+1 + ... + A_0,n*X_n = A_0,0

X₁ + A_1,m+1*X_m+1 + ... + A_1,n*X_n = A_1,0

 .

. . . . . . . . . . . . . . . .

 .

X_i + A_i,m+1*X_m+1 + ... + A_i,n*X_n = A_i,0

.

. . . . . . . . . . . . . . . .

.

X_m + A_m,m+1*X_m+1 + ... + A_m,n*X_n = A_m,0

Данная формальная модель задачи линейного программирования обычно задается в форме так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода:

Симплекс-таблица

Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1, ..., Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm+1, ..., Xn - свободные переменные задачи.

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

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

2.2.2. Геометрический метод

Применяется дя задач с двумя переменными. Метод решения состоит в следующем:

На плоскости Ох1х2 строятся прямые, которые задают соответствующие ограничения:

a11 x1 + a11 x2 + …… + a11 xn = b1 ,

a21 x1 + a22 x2 + …… + a2n xn = b2 ,

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

am1 x1 + am2 x2 + …… + amn xn = bm .

Находим множество всех точек х1,х2, удовлетворяющим всем неравенствам. Такое множество называется областью допустимых решений. Строим вектор  и перемещаем линию уровня, который задается уравнением: с1х1+с2х2 = const в направлении вектора до последней точки пересечения с ОДР. Эта точка и дает решение задачи Lmax = значению L в этой точки

2.3. Двойственная задача.

Общая схема построения двойственной задачи.

Если задана общая задача ЛП:

где D определяется системой уравнений и неравенств:

 то двойственной по отношению к ней называется общая задача ЛП:

где D* определяется системой уравнений и неравенств:

 Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

3. Матрица ограничений задачи А транспонируется.

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

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

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

((D*)*, (f*)*)≡(D, f),

Основные теоремы:

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

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

Теорема 3 (об оценках). Значение переменных  в оптимальном решении двойственной задачи представляет собой оценки влияния свободных членов bi в системе ограничения прямой задачи на величину целевой функции f(x*)

Похожие работы

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

Скачать

32249

6

16

... лучей, исходящих из одной точки, называется многогранным выпуклым конусом с вершиной в данной точке.   1.4 Математические основы решения задачи линейного программирования графическим способом   1.4.1 Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = ...

Решение задачи линейного программирования графическим методом

Скачать

40640

2

10

... игр, теория массового обслуживания, и др. 1. ПОСТАНОВКА ЗАДАЧИ   Целью нашего курсового проекта является решение задачи линейного программирования графическим методом. 1.1    Математическое программирование. Математическое программирование ("планирование") – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ...

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

Скачать

25011

8

6

... . 1.3. Построение ограничений и градиента целевой функции : 1.4. Область допустимых решений – отрезок AB. 1.5. Точка А – оптимальная. Координаты т. А: ; ; . 2. Решение задачи линейного программирования симплекс-методом. Прямая задача. Задачу линейного программирования для любой вершины в компактной форме можно представить в виде: Для получения используем алгоритм, приведённый в ...

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

Скачать

36149

6

0

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