СКАЧАТЬ:  2_laba_712.zip [257,39 Kb] (cкачиваний: 55)

Лабораторная работа №2

по дисциплине «Моделирование систем»

на тему: «Решение задач линейного программирования, отыскание экстремумов функции симплекс-методом» 

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

Основные сведения из теории.

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

В задачах линейного программирования критерий оптимальности

                                                   (1) 

где С – заданный коэффициент, который может быть отрицательным и положительным.

Выражение (1) называют линейной формой.

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

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

                                (2)

a₁₁…a_mn – могут быть как отрицательными, так и положительными;

b₁…b_m – только положительные.

Если x₁…x_n рассматриваем как параметры какого-либо технологического процесса, то они должны быть неотрицательными:

Если ограничение задано в виде неравенства, то его необходимо преобразовать в равенство, путем добавления ещё одной переменной х_n+1. Эта переменная называется выравнивающей или балансовой.

Например, для неравенства (1) из системы (2) можем записать:

Для выражения (2) в системе (2) можно записать:

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

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

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

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

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

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

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

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

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

                      (3)

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

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

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

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

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

                             (4)

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

                                       (5)

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

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

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

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

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

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

Расчетная часть.

Задача 7.

Найти оптимальные неотрицательные решения, максимизирующие линейную форму:

x₁ -2х₂ +3x₃ ≥ -1

2x₁ - х₂ – x₃ ≤ -1

L = -х₁ - 2x₂ - 3x₃

Решение:

1. Приведем систему к новому виду, представив ограничения, записанные в виде неравенств, к ограничениям, заданным в виде равенств:

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

2x₁ - х₂ – x₃ + x₅ = -1

L = -х₁ - 2x₂ - 3x₃

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

Так как ранги совпадают, система совместна. Число базисных переменных равно 2.

3. Примем за базисные переменные x₂ и x₃, за свободные x₁, x₄ и х₅. Выразим базисные переменные через свободные. Сначала выразим из первого и второго уравнения переменную x₂ и, приравняв их правые части, выразим переменную x₃:

Точно так же выразим из первого и второго уравнения переменную x₃ и, приравняв их правые части, выразим переменную x₂:

Выразим целевую функцию в новых переменных:

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

L(0, 4/5, 1/5, 0, 0) = -11/5        при x₁=0, x₄=0 и x₅=0           

Ответ: Базисное решение (0, 4/5, 1/5, 0, 0) является оптимальным, так как критерий окончания поиска максимума целевой функции (значения коэффициентов в целевой функции отрицательные) выполнен и найденное решение неотрицательно. Максимальное значение целевой функции равно -11/5.