Скачать:  zadachi-123.zip [292,24 Kb] (cкачиваний: 13)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РТ

ЛАБОРАТОРНАЯ РАБОТА №1

ПО ДИСЦИПЛИНЕ «МОДЕЛИРОВАНИЕ СИСТЕМ»

«ОТЫСКАНИЕ ЭКСТРЕМУМОВ ФУНЦИИ СИМПЛЕКС-МЕТОДОМ»

СИМПЛЕКСНЫЙ МЕТОД

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

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

Понятие о симплекс-методе

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

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

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

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

Алгоритм симплекс метода

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

(1)

и среди неотрицательных решений системы уравнений (1) надо найти такое, которое бы максимизировали или минимизировали линейную функцию

Рассмотрим решение поставленной задачи с использованием симплекс метода подробно. Алгоритм решения состоит из следующих этапов.

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

Ограничительные условия могут задаваться и смешанным образом, т. е. неравенствами и уравнениями. Тогда указанным способом их можно всегда свести к ограничениям вида (1).

Работа симплекс-метода начинается с выбора опорного решения, содержащего r базисных переменных и n-r свободных переменных. Так как в задаче имеется r уравнений-ограничений, то неизвестные переменные х_1….x_r (r<=m) можно выразить через остальные n-r переменные и уравнения-ограничения могут быть преобразованы к следующему виду:

(2)

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

(3)

Теперь, полагая все свободные переменные равными нулю, найдём значения базисных переменных . Таким образом, решение системы является допустимым — оно называется базисным. Подставляя в линейную форму 1 значения базисных переменных, получим базисное значение линейной формы для полученного базисного решения

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

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

Таким образом, далее меняем одну из свободных переменных с таким расчётом, чтобы значение уменьшалось, или, по крайней мере, не увеличивалось, если нами решается задача на нахождение min l, т.е. переходим к новому базису В’ такому, что . Процесс продолжается итеративно до тех пор, пока все коэффициенты в уравнении (3) не станут положительными.

Если ищется mах l, то переход к новому базису В’ осуществляется так, чтобы выполнялось неравенство Соответственно, процесс продолжается до тех пор, пока все коэффициенты в уравнении (3) не станут отрицательными.

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

Задача 2.

Минимизировать линейную форму при заданных ограничениях

x₁ = 2 +2 x₃ - x₄

x₂ = 1+ x₃ – 2x₄

x₅ = 5 - x₃ + x₄

L = x₁ + x₂

Решение:

1.Определим, имеет ли система общее решение. Определим ранг системы

Так как rank расширенной матрицы и матрицы равны, следовательно, система совместна. Rank равен 3, значит, число базисных переменных равно 3.

2. Примем за базисные переменные x₁ , x₂, x₅; за свободные x₃ ,x₄.

x₁ =2 +2 x₃ - x₄

x₂ = 1+ x₃ – 2x₄

x₅ = 5 - x₃ + x₄

L = x₁ + x₂ = 2 +2 x₃ - x₄ + 1+ x₃ – 2x₄ = 3+ 4x₃ – 3x₄

3. Найдем первое допустимое решение:

(2, 1, 0, 0,5) при x₄=0 и x₃=0

Для данного решения найдем целевую функцию L= 3+0-0=3

Минимальную целевую функцию мы получим, если будем увеличивать x₄. Определим, до какого значения можно увеличивать x₄.

0 = 2 - x₄ x₄ = 2

0 = 1 – 2x₄x₄ = 1/2

0 = 5 + 0 x₄ = -5

x₁ = 2 – 2 = 0 x₁ = 2 – 1/2 = 3/2 x₁ = 2 – (-5) = 7

x₂ = 1 – 4 = -3 x₂ = 1 – 1 = 0 x₂ = 1 + 10 = 11

x₅ = 5 + 2 = 7 x₅ = 5 + 1/2 = 11/2 x₅ = 5 -5 = 0

x₄ увеличиваем до 1/2, т.к при этом условии переменные будут неотрицательны, но при этом x₂ = 0. Теперь x₄ – базисная, x₂ – свободная переменная.

x₁ = 3/2+ 3x₃/2 + x₂/2

x₄ = 1/2 +x₃/2 - x₂/2

x₅ = 11/2 - 3x₃/2 -x₂/2

L = 3 + 4x₃ – 3 (1/2 +x₃/2 - x₂/2) = 3/2 + 5/2x₃ + 3/2

При x₂ = x₃ = 0 L = 3/2

Дальнейшее увеличение невозможно, т.к.коэффициенты в целевой функции положительны.

Таким образом, x₁ = 3/2, x₂ = 0, x₃ = 0, x₄ = 1/2, x₅ = 11/2 являются оптимальными переменными, обеспечивающие минимальное значение L = 3/2

Задача 3.

Минимизировать линейную форму при заданных ограничениях.

2x₁ + x₂ - x₃ - x₄=2

x₂ - x₄=1

L = 2x₃ - x₂

Решение:

1. Определим, имеет ли система общее решение. Определим ранг системы.

Так как rank расширенной матрицы и матрицы равны, следовательно, система совместна. Rank равен 2, значит, число базисных переменных равно 2.

2. Примем за базисные переменные x₁ и x₂, за свободные x₃ и x₄.

x₁ = (1+x₃)/2

x₂ = 1+ x₄

L = 2x₃ – 1 - x₄

3. Найдем первое допустимое решение:

(1/2, 1, 0, 0) при x₄=0 и x₃=0

Для данного решения найдем целевую функцию L= 0-1-0= -1.

Минимальную целевую функцию мы получим, если будем увеличивать x₄. Определим, до какого значения можно увеличивать x₄.

0= 1+ x₄, x₄ =-1

0= (1+0)/2

x₁ = 1/2

x₂ = 1-1=0

x₄ увеличиваем до -1, т.к. при этом условии переменные будут неотрицательны, но при этом x₂=0, следовательно, теперь x₄ является базисной, а x₂ – свободной.

Переходим к новому решению:

x₁ = (1+x₃)/2

x₄ = x₂ - 1

Дальнейшие преобразования ни к чему не приведут, т.к. переменные x₄ , x₂

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

Задача 1.

Минимизировать линейную форму при заданных ограничениях.

x₁ - 2x₂ -+x₃ =1

x₁ +3x₂ + x₄=2

L = x₁ -x₃

x_j≥0

j=1,4

Решение:

1.Определим, имеет ли система общее решение. Определим ранг системы.

Так как rank расширенной матрицы и матрицы равны, следовательно, система совместна. Rank равен 2, следовательно, две базисные переменные можно выразить линейно через другие две свободные.

2. Примем за базисные переменные x₃ и x₄, за свободные x₁ и x₂.

x₃ = 1+2x₂- x₁

x₄ = 2-3x₂ – x₁

L =-1-2x₂-+2x₁

3. Найдем первое допустимое решение:

(0, 0, 1, 2) при x₄=0 и x₃=0

Для данного решения найдем целевую функцию L= -1.

Минимальную целевую функцию мы получим, если будем увеличивать x₂. Определим, до какого значения можно увеличивать x₂.

0= 1+ x₂, x₂ =2/3

0= 2-3x₂;

x₂ = -1/2

x₂ = 2/3

x₂ увеличиваем до 2/3.

Т.о. получаем следующие значения переменных x₁ = 0, x₂ =2/3, x₃=7/3, x₄ = 0, или что одно и тоже (0; 2/3; 7/3; 0). Значение линейной формы L при допустимом решении равно L=-7/3. Т.е. величина L при втором шаге уменьшилась.

Далее, примем за свободные переменные х₁, х₄

x₃ =7/3-2/3x₄-5/3х₁,

x₂ =2/3-1/4x₄ -1/3х₁;

L=-7/3+8/3х₁+2/3х₁.

Т.к. в последней линейной форме обе свободные переменные входят с положительными коэффициентами, то наименьшее значение достигается при x₁ = 0,x₄ = 0. Это означает, что решение (0; 2/3; 7/3; 0) является оптимальным и L_min=-7/3.