Реализация симплекс в случае положительных свободных членов

Содержание

Введение 2

Теоретическая часть. Реализация симплекс в случае 
положительных свободных членов  3

Практическая  часть 10

Заключение   13

Литература 14 

 

Введение

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

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

В общем  виде математическая постановка задачи математического программирования состоит в определении наибольшего или наименьшего значения целевой функции f (х₁, х₂, ..., х_n) при условиях g_i(х₁, х₂, ..., х_n) £ b_i;  
(i =1,2,…m), где f и g_i; – заданные функции, а b_i – некоторые действительные числа. 

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

    В данной работе рассматривается задача линейного программирования и метод  ее решения – симплексный метод (симплекс-метод).

 

     Теоретическая часть. Реализация симплекс в случае положительных свободных членов 

    Общая задача линейного программирования (ЗЛП) формулируется следующим образом. 

    Дана  система m линейных уравнений и неравенств с n переменными (система ограничений)

 (1)

и линейная функция 

               F=c₁x₁+ c₂x₂+…+ c_nx_n. (2)

    Необходимо  найти такое решение системы X=(x₁, x₂, …, x_n),  
где

               x_j ≥0 (j=1,2,…,l; l≤n),  (3)

при котором линейная функция F принимает оптимальное (то есть максимальное или минимальное) значение.

    Система (1.1) называется системой ограничений, а функция F  - целевой функцией.

    Опр.: Оптимальным решением (или оптимальным планом) ЗЛП называется решение X=(x₁, x₂, …, x_n) системы ограничений (1), удовлетворяющее условию (3), при котором линейная функция (2) принимает оптимальное (максимальное или минимальное) значение.

    ЗЛП называется стандартной, если все переменные x_j ≥0  и система (1)  состоит из одних неравенств.

    ЗЛП называется канонической, если все переменные x_j ≥0  и система (1)  состоит из одних уравнений.

    Любая задача может быть сведена к канонической, стандартной или общей задаче.

    Рассмотрим  систему m линейных уравнений с n неизвестными.

 (4)

    Опр.: Рангом R матрицы системы (4)  называется наивысший порядок ее миноров, отличных от нуля.

    В ЗЛП представляют интерес системы, у которых ранг R<n.

    В дальнейшем будем полагать, что  R=m и m<n.

    Любые m переменных системы (4) называются основными (ОП) или базисными, если определитель матрицы коэффициентов при них отличен от 0. Тогда остальные n-m переменных называются неосновными (НП) или свободными.

    Максимально возможное число групп ОП равно  числу сочетаний .

    Так как могут встретиться случаи, когда определитель матрицы коэффициентов при m переменных равен 0, то общее число групп ОП ≤ .

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

    Опр.: Решение X=(x₁, x₂, …, x_n) системы (4) называется допустимым, если содержит лишь x_j ≥0 (j=1,…, n). В противном случае – решение недопустимое.

    Решение X=(x₁, x₂, …, x_n) системы (4), в котором все неосновные переменные равны 0, называется базисным.

    В ЗЛП представляют интерес допустимые базисные решения (опорные планы).

    Число базисных решений конечно и ≤  .

    Базисное  решение, в котором ходя бы одна из ОП равна 0, называется вырожденным.

    Вывод: совместная система (4) имеет бесконечно много решений, из них базисных решений конечное число, меньшее или равное .

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

    Теорема. Каждому допустимому базисному решению ЗЛП соответствует угловая точка многогранника решений и, наоборот, каждой угловой точке многогранника решений соответствует  допустимое базисное решение.

    Вывод: Если ЗЛП имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений. То есть  оптимум линейной функции ЗЛП следует искать среди ее допустимых базисных решений, которых конечное число.

    Существует, так называемый симплексный метод  решения ЗЛП,  основанный на приведенной  выше теореме.

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

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

    Поэтому опишем шаги аналитического симплексного метода на примере.

    Требуется найти решение ЗЛП:

    

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

    

    2 Шаг: Число основных переменных (ОП) задачи  должно быть равно количеству уравнений системы, то есть трем. Выберем их. В качестве ОП на этом шаге следует выбрать такие m=3 переменных, каждая из которых

1. входит только в одно из m=3 уравнений системы ограничений;
2. имеет тот же знак, что и свободный член соответствующего уравнения системы.

Такими  переменными, очевидно, являются дополнительные переменные.

То есть ОП: . Соответственно, неосновные переменные (НП):  . Выразим ОП через НП:

      (5)

    НП  в допустимом базисном решении принимают  значения 0, тогда  .

    Получили  допустимое базисное решение: .

    Целевая функция выражена через НП и равна .

    3 Шаг: Поскольку функция F стремится к максимуму, то ее значение можно увеличить, переведя одну из НП, через которые она выражена, в ОП. При этом перевод переменных х₁ или х₂ в ОП приведет к увеличению ее значения, так как знаки коэффициентов перед ними положительные, а ОП принимают положительные значения. А перевод х₃ в ОП приведет к уменьшению  значения F, так как коэффициент в F перед х₃ отрицательный.  

    Можно сделать вывод: решение является оптимальным, если при поиске максимума (минимума) в целевой функции, выраженной через НП, нет ни одного положительного (отрицательного) коэффициента.

    В нашем случае, решение не является оптимальным,  так как коэффициенты  при х₁ и х₂ в F положительные.

    4 Шаг: Среди НП переводится в ОП та, у которой самый большой по модулю отрицательный (при поиске минимума) или положительный (при поиске максимума) коэффициент в целевой функции, выраженной через НП.

    В нашем случае – это переменная х₁.

    5 Шаг: Определим, какая переменная должна выйти из базиса, то есть перейти из ОП в НП.

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

      (6)

    Переменные  х₂ и х₃ остаются неосновными, следовательно равны 0.

    Последняя система неравенств преобразуется  в

      

    Последнее неравенство выполнено при любых  значениях х₁, следовательно, х₆ от х₁ не зависит и х₁ может увеличиваться до .

    Верхняя граница  =1,5. Переменная х₅ уходит в НП. Второе уравнение системы (5) называется разрешающим.

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

    6 Шаг:   Выразим х₁ через х₅ в разрешающем уравнении, а затем и все остальные ОП через х₅.

      (7)

    Выразим целевую функцию через НП:

     . (8)

    Получили  допустимое базисное решение: .

    

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

    Пройдем эти шаги.

      не является оптимальным,  так как в целевой функции  F (см. (8)) есть переменная х₂, коэффициент перед которой положительный.

    Переменную  х₂ переводим в ОП. Определим верхнюю границу х₂ и переменную, выходящую из ОП в НП. Составим систему неравенств

      или 

     .

    Следовательно, третье уравнение в системе (7) разрешающее  и х₆ выходит в НП.

    Выразим в разрешающем уравнении х₂ через х₆. Затем все остальные ОП через х₆:

    

    Выразим целевую функцию через НП:

      (5)

    Получили  допустимое базисное решение: .

    

    Данное  решение является оптимальным, так  как в выражении (8) целевой функции  нет положительных коэффициентов. Максимальное значение целевой функции  равно 8.

    Приведенные рассуждения удобно представить  в табличном виде.