Алгоритм решения задач симплексным методом. 2

Содержание

 

Введение………………………………………………………………………………..3                                                                                                                                                                                                                                                                                                                                                  

1 Описание симплексного метода..…………...……………………………...……….4

2 Алгоритм решения задач симплексным методом……………………...…………..9

2.1 Графический метод……………………………………………………………….16

2.2 Табличный симплекс – метод……………………………………………….…...21

2.3 Алгоритм метода искусственного базиса………………...…………….……….25

2.4 Двойственный симплекс-метод………………..………………………………...26

3 Решение реальной производственной задачи…………………………………….28

3.1 Постановка задачи………………………………………………………………..28

3.2 Решение задачи…………………………………………………………………...28

Заключение……………………………………………………………………………38

Список используемой литературы…………………………………………………..40

 

Введение

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

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

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

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

 

1 Описание симплексного метода

 

Симплекс - выпуклый многоугольник в n-мерном пространстве с n + 1 вершинами, не лежащими в одной гиперплоскости. Симплексы выделены в отдельный класс потому, что в n-мерном пространстве n точек всегда лежат в одной гиперплоскости(гиперплоскость делит пространство на два полупространства). Так что симплекс - это простейший многоугольник, содержащий некоторый объем n-мерного пространства.

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

Задача линейного программирования (далее ЛП) состоит в необходимости максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.

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

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

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

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

При решении задач линейного программирования все ограничения, имеющие вид неравенств, преобразуют в равенство путем:

1) Добавления неотрицательной остаточной переменной в левую часть неравенства вида « ≤ ».

2) Вычитания неотрицательной избыточной переменной из левой части неравенств вида « ≤ ».

Избыточные и достаточные переменные называют свободными.

Кроме того, все элементы правой части bi делают неотрицательными, либо умножая для этого i-ое уравнение на -1, если bi < 0, либо используя эквивалентность следующих отношений:

                                           (1.1)

Запишем целевую функцию:

F(X) =c1x1+c2x2+...+cnxn => max,                                                                       (1.2)

Где F(X) – целевая функция.

        ci – коэффициенты при переменных.

        xn – базисные переменные.

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

 

a11x1 + a12x2 + . . . + a1nxn ≤ b1

a21x1 + a22x2 + . . . + a2nxn ≤ b2

. . . . . . . . . . . . . . . . . . . . . . . . .                                                                            (1.3)

am1x1 + am2x2 + . . . + amnxn ≤ bm                                                                           

 

xj ≥ 0, (j = 1, 2, . . . n)                                                                                         (1.4)                                                     

 

 

 

Запишем представленную систему ограничений в канонической форме:

a11 x 1+a12 x 2+...+a1n x n = b1

a21 x 1+a22 x 2+...+a2n x n = b2                                                                         (1.5)

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

am1 x 1+am2 x 2+...+amn x n = bm

 

Пусть A = (Аij) — матрица m*n, B = (b1, … , bm)T — вектор-стоблец,                  C = (c1, … , cn) — вектор-строка. Если A = (a1, … , am) и A = (b1, … , bm), то под неравенством A ≥ B будем понимать m неравенств ai ≥ bi (i = 1, … , m).

Используя матричные операции, запишем стандартную и каноническую задачу ЛП в матричном виде:

C∙X→max         Целевая функция                                                               

A∙X≤B               Система ограничений                                                           (1.6)

X≥0                  Условие неотрицательности

 

Матрица A = (aij) (i = 1, … , m; j = 1, 2, . . . n), составленная из коэффициентов системы (1.5), называется симплекс-таблицей.

Таблица 1.1.  Начальная симплекс-таблица.

Базисные Переменные	Свободные Переменные	X1	.......	Xi	.......	Xm
X1	b1	1	.......	0	.......	0
X2	b2	0	.......	0	.......	0
.....	.....	.....	.....	.....	.....	.....
Xi	bi	0	.......	1	.......	0
.....	.....	.....	.....	.....	.....	.....
Xm	bm	0	.......	0	.......	1
F(X)	C0	0	.......	0	.......	0

 

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

Переход от текущей базы к соседней называется итерацией.

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

1. Определить число и состав базисных и свободных переменных.
2. Выразить базисные переменные через свободные переменные.
3. Выразить целевую функцию через свободные переменные.
4. Построить начальную симплекс-таблицу.
5. Проверить решение на оптимальность: если в F-строке (кроме С0) все Сj=0, то получено оптимальное решение: X=(B1,...,Bm,0,...,0), F=C0. Если же существует Cj<0, то решение можно улучшить, но предварительно надо проверить факт существования решения.
6. Проверить существование решения: рассмотрим все столбцы, у которых Сj<0, если существует хотя бы один столбец, у которого все коэффициенты Aij<0, то задача решения не имеет, т.к. множество допустимых решений D не ограничено и целевая функция неограниченно возрастает. Если таких столбцов нет, то переходим к следующему этапу. Выбрать свободную переменную, которую надо ввести в базис (выбор разрешающего столбца): это столбец с минимальным значением Сj (пусть это k-й столбец). Выбрать базисную переменную, которую надо вывести из базиса (выбор разрешающей строки). Рассмотрим k-й столбец и все его элементы, которые больше нуля, т.е. Aik>0. Для всех этих элементов находим отношение Bi/Aik и выбираем строку, которая соответствует минимальному значению этого отношения (пусть это i-я строка). Соответствующая i-я переменная Xi выводится из базиса, при нескольких одинаковых отношениях берем любую строку. Элемент Aik называется разрешающим элементом.
7. Пересчитать симплекс-таблицу.

• составляем новую симплекс-таблицу, заменив в составе базисных переменных Xi на Xk;

• заполняем сначала новую k-ю строку, записывая в нее элементы старой     i-ой строки, поделенные на разрешающий элемент;
• после заполнения k-ой строки заполняем оставшиеся строки. Для этого k-ю строку умножаем последовательно на такие числа, чтобы после сложения ее с каждой строкой старой таблицы в k-ом столбце получить везде ноль (кроме единицы в k-ой строке).

8. После заполнения новой симплекс-таблицы алгоритм возвращается к 5-му пункту.

Конец работы алгоритма:

• либо когда в F-строке все коэффициенты (кроме С0) будут больше нуля, тогда получаем оптимальное решение;
• либо когда существует столбец, у которого Cj<<0 и все коэффициенты Aij<<0, в этом случае решения не существует.

 

 

2 Алгоритм решения задач симплексным методом

 

Формализованный алгоритм симплекс-метода состоит из двух основных этапов:

1) построение опорного плана;

2) построение оптимального плана.

Алгоритм симплекс-метода рассмотрим на примере реальной задачи.

Пусть предприятие может изготавливать изделия четырех видов: U1, U2, U3, U4. Для изготовления каждого изделия требуется определенный вид оборудования. Известно, сколько времени требуется на изготовление каждого изделия на каждом оборудовании и какая прибыль может быть получена при реализации каждого изделия. Требуется так распределить изделия по видам оборудования, чтобы предприятие имело максимальную прибыль.

Таблица 2.1. Распределение изделий по видам оборудования.

	U 1	U2	U3	U4	bj
b1	3	5	2	7	15
b2	4	3	3	5	9
b3	5	6	4	8	8
сj	40	50	30	20

 

Где bj - ресурсы оборудования ;

       aij - время изготовления j-ого изделия на i-ом оборудовании;

       cj - прибыль от одного изделия Uj;

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

F(x)= 40x1 + 50х2 + 30х3 + 20х4→ max                                                               (2.1)

3x1 + 5x2 + 2x3 + 7x4 ≤ 15

4x1 + 3x2 + 3x3 + 5x4 ≤ 9                                                                                      (2.2)

5x1 + 6x2 + 4x3 + 8x4 ≤ 30

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

a15=1, a25=0, a35=0

a16=0, a26=1, a36=0

a17=0, a27=0, a37=1

 

Тогда система равенств и условие неотрицательности запишется в виде:

3*x1 + 5*x2 + 2*x3 + 7*x4 + 1*x5 + 0*x6 + 0*x7 = 15

4*x1 + 3*x2 + 3*x3 + 5*x4 + 0*x5 + 1*x6 + 0*x7 = 9                                           (2.3)                    

5*x1 + 6*x2 + 4*x3 + 8*x4 + 0*x5 + 0*x6 + 1*x7 = 30

 

                                                                                                                             (2.4)

 

Целевая функция запишется следующим образом:

                                       

                                                                                                                             (2.5)

При этом: с5 = c6 = c7 = 0

Таким образом, задача распределения продукции по видам оборудования сводится к нахождению таких значений переменных xj (j от 1 до n), которые удовлетворяют системе равенств вида (2.3), дополнительным ограничениям (2.4) и максимизируют прибыль предприятия вида (2.5).

Решение общей распределительной задачи выполняется в два этапа:

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

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

В нашем случае базис выражается легко, его составляют дополнительно введенные свободные переменные x5, x6, x7. Выразим их через остальные и результат запишем в форме Таккера2:

x5 = 15 - (3x1 + 5x2 + 2x3 + 7x4)

x6 = 9 - (4x1 + 3x2 + 3x3 + 5x4)                         

x7 = 30- (5x1 + 6x2 + 4x3 + 8x4)

В нашем случае x5, x6, x7 называются базисными и соответственно x1, x2, x3, x4 небазисными переменными. Для получения опорного плана надо приравнять к нулю небазисные переменные, тогда получим:

Х = (0; 0; 0; 0; 15; 9; 30)

Опорный план получен, и первый этап решения задачи завершен.

На втором этапе (улучшение опорного плана) можно использовать несколько способов, однако на практике чаще всего используют симплекс-метод.

1) Выражение целевой функции  через небазисные переменные:

Y = 40x1 + 50x2 + 30x3 + 20x4

Записать целевую функцию в форме Таккера:

Y = 0 - (-40x1 - 50x2 - 30x3 - 20x4)

2) Проверка базисного решения  на оптимальность. Если в полученном  выражении целевой функции, записанной  в форме Таккера, все коэффициенты  при небазисных переменных неотрицательны (≥ 0), то исходный базис является оптимальным и находится соответствующее оптимальное базисное решение, минимизирующее целевую функцию. Для этого всем небазисным переменным присваивается значение равное 0, а все базисные переменные находят из системы ограничений, и одновременно определяется целевая функция. Если в полученном выражении целевой функции хотя бы один коэффициент при небазисных переменных отрицателен, то переходят к следующему этапу.

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

4) Выбор из небазисных переменных  той, которая способна при введении  её в базис увеличить значение  целевой функции. Наиболее часто  на практике в качестве такой  переменной выбирают ту, которой  соответствует наибольший отрицательный  коэффициент целевой функции. Следовательно, в базис вводится x2.

5) Определение, какая из базисных  переменных должна быть выведена  из базиса. Для всех положительных  коэффициентов столбца при вводимой  переменной в системе ограничений  находят отношение свободного  члена соответствующему коэффициенту столбца. Минимальное из полученных соотношений указывает строку выводимой переменной. 15/5; 9/3; 30/6 - в соответствии с этими отношениями из базиса выводим х5.

6) Выражение вводимой в базис  переменной через выводимую и  другие небазисные переменные.

x2 = 3 - (3/5x1 + 2/5x3 + 7/5x4 + 1/5x5)

7) Выражение остальных базисных  переменных х6, х7 и целевой функции через новые небазисные переменные х1, х3, х4, х5:

x6 = 0 - (11/5x1 + 9/5x3 + 4/5x4 - 3/5x5)

x7 = 12 - (1/5x1 + 8/5x3 - 2/5x4 - 6/5x5)

Y = 150 - (-10x1 - 10x3 + 50x4 + 10x5)

8) Повторение операций пунктов 2) - 7) до тех пор, пока не будет найдено оптимальное решение.

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

1) Привести задачу к каноническому виду;

2) Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решения ввиду несовместимости системы ограничений);

3) Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода;

4) Если выполняется признак единственности оптимального решения, то решение задачи заканчивается;

5) Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.

 

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

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

а) правые части условий (свободные члены bi) являются величинами неотрицательными;

б) сами условия являются равенствами;

в) матрица условий содержит полную единичную подматрицу.

Если свободные члены отрицательные, то обе части неравенства умножаются на – 1, а знак неравенства меняется на противоположный. Для преобразования неравенств в равенства вводятся дополнительные переменные, которые, обычно, обозначают объем недоиспользованных ресурсов. В этом и состоит их экономический смысл.

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

В оптимальном решении задачи все искусственные переменные (ИП) должны быть равными нулю. Для этого вводят искусственные переменные в целевую функцию задачи с большими отрицательными коэффициентами (-М) при решении задачи на max, и с большими положительными коэффициентами (+М), когда задача решается на min. В этом случае даже незначительное ненулевое значение искусственной переменной будет резко уменьшать (увеличивать) значение целевой функции. Обычно М в 1000 раз должно быть больше, чем значения коэффициентов при основных переменных.

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

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

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

Столбец симплексной таблицы с этим номером на данной итерации называется генеральным столбцом.

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

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

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

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

Значения новых базисных переменных получим в соответствующих ячейках столбца свободных членов.

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

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

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

2) В большинстве случаев оценки параметров модели получаются путём статистической обработки ретроспективных данных. Полученные в результате этого оценки не могут быть абсолютно точными. Если удаётся определить, какие параметры в наибольшей степени влияют на значение целевой функции, то целесообразно увеличить точность оценки именно этих параметров. В конечном счёте, это позволяет повысить надёжность модели и получаемого решения. На данные и многие другие подобные вопросы, связанные с анализом чувствительности, следует ответить, располагая численными данными на заключительной итерации симплекс-метода. К числу наиболее часто решаемых на практике вопросов относятся:

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

б) к каким последствиям приведёт сокращение объёмов ресурсов.

в) что произойдёт, если ввести в рассмотрение новую управляемую переменную.

 

2.1 Графический метод

Алгоритм графического метода решения задач линейного программирования состоит из следующих пунктов:

1)  Построить область допустимых решений.

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

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

 

4) Линию уровня переместить до опорной прямой в задаче на max в направлении нормали, в задаче на min в противоположном направлении.

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