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

Торгово –  экономический колледж казпотребсоюза

Курсовая работа

по дисциплине: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОИЗВОДСТВЕННЫХ И ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ

на тему: понятие о симплекс-методе

Дата:24.01.2014

Оценка:______

Выполнил(а):Вислович Сергей

Проверила: Алиханова М.Н

астана 2014

СОДЕРЖАНИЕ

Введение

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

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

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

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

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

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

І Основные теоретические  положения симплексного метода решения  ЗЛП

1.1 Теория линейного  программирования

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

Решить подобную задачу бывает непросто, особенно при наличии  большого числа вариантов. Время  и затраты при выборе оптимума не всегда оправданны: издержки поиска и перебора вариантов могут превысить  достигнутый выигрыш.Как показывает практика, опыт и интуиция оказываются недостаточными для обоснования оптимального решения.Более надежный и эффективный способ — использование математических (количественных) подходов и расчетов. Однако математические подходы и обоснования длительное время игнорировались теоретиками, делавшими “погоду” в экономической науке. Многие важные работы были заморожены, публикации экономистов-математиков тормозились и ограничивались. И все же в тот период математические изыскания продолжались, даже в условиях гонения на математиков были достигнуты блестящие результаты.Одним из наиболее значительных и ярких достижений в области экономико-математических исследований было открытие Леонидом Витальевичем Канторовичем (1912—1986) Метода линейного программирования.

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

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

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

1.2 Общий вид задач  линейного программирования

В общем случае задача линейного программирования может быть записана в таком виде(формула 1.1)

Z(X)=c₁x₁+c₂x₂+…+c_nx_n→ max(min),      (1.1)

 a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁,

…………………………

a_i1x₁+a_i2x₂+…+a_inx_n=b_i,

a_(i+1)1x₁+a_(i+1)2x₂+…+a_(i+1)nx_n≤b_i+1 (1.2)

………………………..

a_m1x₁+a_m2x₂+…+a_mnx_n≤b_m

x_j≥0, j=1,2,…,t; t≤n. (1.3)

Данная запись означает следующее: найти экстремум целевой функции (1.1) и соответствующие ему переменные X=(X₁, X₂,...,X_n) при условии, что эти переменные удовлетворяют системе ограничений (1.2) и условиям неотрицательности (1.3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X₁, X₂,...,X_n), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений(ОДР).

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

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

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

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

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

Каноническая задача линейного  программирования в координатной записи имеет вид (формула 1.4):

Z(X)=c₁x₁+c₂x₂+…+c_nx_n→ max (1.4)

a₁₁x₁+a₁₂x₂+…+a_1nx_n≤b₁,

a₂₁x₁+a₂₂x₂+…+a_2nx_n≤b₂

_{… …  … … … …  … …}

a_m1x₁+a_m2x₂+…+a_mnx_n≤b_m

x_j≥0, j=1,2,…,n.

Каноническая задача линейного  программирования в матричной записи имеет вид (формулы 1.5, 1.6):

Z(X)=CX → max(min), (1.5)

AX=A₀, Y≥θ,

A=

Здесь:

• А — матрица коэффициентов системы уравнений
• Х — матрица-столбец переменных задачи
• Ао — матрица-столбец правых частей системы ограничений

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

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

Возьмем линейное неравенство a₁x₁+a₂x₂+...+a_nx_n≤b и прибавим.

Это может быть сделано следующим образом: к его левой части некоторую величину x_n+1 , такую, что неравенство превратилось в равенство a₁x₁+a₂x₂+...+a_nx_n+x_n+1=b. При этом данная величина x_n+1 является неотрицательной.

1.3 Методы решения задач  линейного программирования

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

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

Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа  2Х₁  + 5Х₂   ≤ 10,       то, очевидно,  0 ≤ Х₁  ≤ 10/2 = 5 и 0 ≤ Х₂  ≤ 10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.

Проведем перебор точек  параллелепипеда с шагом 1/10ⁿ последовательно при n=2,3,…, вычисляя значения целевой функции и проверяя наличие ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10ⁿ).

Направленный перебор.Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆ ; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)

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

1.4 Общая характеристика симплекс-метода

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

Рисунок 1.1 – Переход от одной вершины к другой

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

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала. 

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит:

- умение находить начальный опорный план;

- наличие признака оптимальности опорного плана; 

ІІ РЕШЕНИЕ ЗЛП СИМПЛЕКСНЫМ МЕТОДОМ

2.1 Примеры использования симплекс-метода в экономике

Задачи ЛП нашли широкое применение в экономике. Рассмотрим это на примерах.

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

Пример 2. Группа истребителей поднимается в воздух для перехвата одиночного самолёта противника. Цель операции - сбить самолёт. Показатель эффективности - вероятность поражения цели.

Пример 3. Ремонтная мастерская занимается обслуживанием машин; её рентабельность определяется количеством машин, обслуженных в течение дня. Показатель эффективности - среднее число машин, обслуженных за день.

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

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

Пример 6. Проводится борьба за экономию средств при производстве определённого вида товара. Показатель эффективности - количество сэкономленных средств.

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

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

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

2.2 Алгоритм решения ЗЛП симплексным методом

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

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

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

Таблица 2.1 –Пример симплекс-таблицы

Третий шаг. На третьем шаге пересчитываем всю симплекс-таблицу по специальным формулам.

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

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

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

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

Идея симплекс-метода относительно проста. Пусть в задаче линейного программирования имеется  п переменных и т независимых  линейных ограничений, заданных в форме уравнений. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где по крайней мере k = n - m из переменных равны нулю. Выберем какие-то к переменных в качестве свободных и выразим через них остальные т базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n - m переменныхx₁, x₂,…,x_k,а

остальные m выражены через  них(формула 2.1):

x_k+1=α_k+1.1x₁+α_k+1.2x₂+   +α_k+1.kx_k+β_k+1;

x_k+2= α_k+2.1x₁+α_k+2.2x₂+   +α_k+2.kx_k+β_k+2;(2.1)

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

x_n= α_n1x₁+α_n2x₂+   +α_nkx_k+β_n.

Предположим, что все  свободные переменныеx₁, x₂,…,x_kравны нулю.

При этом мы получим:

x_k+1=β_k+1;

x_k+2=β_k+2;

…….. (2.2)

X_n=β_n

Это решение может  быть допустимым или недопустимым. Оно допустимо, если все свободные членыβ_k+1, β_k+2,…,β_n(2.2)неотрицательны. Предположим, что это условие выполнено. Тогда мы получили опорное решение. Но является ли оно оптимальным? Чтобы проверить это, выразим целевую функцию Z через свободные переменныеx₁, x₂,…,x_k.

Z=γ₀+γ₁x₁+γ₂x₂+…+γ_kx_k (2.3)

Очевидно, что приx₁=x₂=…=x_k=0, Z=γ₀. Проверим, может ли быть улучшено решение, т. е. получено уменьшение функции Z c увеличением каких-нибудь из переменныхx₁, x₂,…, x_k(2.2) (уменьшать их мы не можем, так как все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициентыγ₁,γ₂,…,γ_kв (2.3) положительны, то увеличение каких-либо из переменныхx₁,x₂,…,x_k(2.2) не может уменьшить Z; следовательно, найденное опорное решение является оптимальным. Если же среди коэффициентовγ₁,γ₂,…,γ_kесть отрицательные, то, увеличивая некоторые из переменныхx₁,x₂,…,x_k(те, коэффициенты при которых отрицательны), мы можем улучшить решение.

Пусть, например, коэффициентγ₁в (2.3) отрицателен. Значит, есть смысл увеличитьx₁, т. е. перейти от данного опорного решения к другому, где переменнаяx₁не равна нулю, а вместо нее равна нулю какая-то другая. Однако увеличиватьx₁следует с осторожностью, так чтобы не стали отрицательными другие переменныеx_k+1, x_k+2,…,x_nвыраженные через свободные переменные, в частности черезx₁формулами (2.2).

Например, если коэффициент  приx₁в соответствующемx_jуравнении (2.2) отрицателен, то увеличениеx₁может сделатьx_jотрицательным. Наоборот, если среди уравнений (2.2) нет уравнения с отрицательным коэффициентом приx₁то величинуx₁можно увеличивать беспредельно, а, значит, линейная функция Z не ограничена снизу и оптимального решения ОЗ не существует.

Допустим, что это не так и что среди уравнений (2.2) есть такие, в которых коэффициент приx₁отрицателен. Для переменных, стоящих в левых частях этих уравнений, увеличениеx₁опасно — оно может сделать их отрицательными.

Возьмем одну из таких  переменныхx_lи посмотрим, до какой степени можно увеличитьx₁, пока переменнаяx_lне станет отрицательной. Выпишемl-eуравнение из системы (2.2):

x_l=α_l1x₁+α_l2x₂+…+α_lkx_k+β_l (2.4)

Здесь свободный членβ_l≥0, а коэффициентα_l1отрицателен.

Легко понять, что если мы оставимx₂=x₃=…=x_k=0, тоx_kможно увеличивать только до значения, равного–β_l/α_l1,а при дальнейшем увеличенииx₁переменнаяx₁станет отрицательной.

Выберем ту из переменныхx_k+1,x_k+2,…,x_n, которая раньше всех обратится в нуль при увеличении x₁, т. е. ту, для которой величина–β_l/α_l1 наименьшая. Пусть это будетx_r. Тогда имеет смысл разрешить систему уравнений (2.2) относительно других базисных переменных, исключаяиз числа свободных переменныхx₁и переводя вместо нее в группу свободных переменныхx_r. Действительно, мы хотим перейти от опорного решения, задаваемого равенствамиx₁=x₂=…=x_n=0 к опорному решению, в котором ужеx₁≠0, аx₂=…=x_k=x_r=0. Первое опорное решение мы получили, положив равными нулю все прежние свободные переменныеx₁,x₂,…,x_kвторое мы получим, если обратим в нуль все новые свободные переменныеx₂,x₃,…,x_k,x_r.

Базисными переменными  при этом будутx_l,x_k+1,x_k+2,…,x_r-1, x_r-1,…,x_r.

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

Пример 2. Пусть имеется задача линейного программирования с ограничениями-неравенствами:

-5x₁-x₂+2x₃≤2;

-x₁+x₃+x₄≤5; (2.5)

-3x₁+5x₄≤7.

Требуется минимизировать линейную функцию

Z=5x₁-2x₃

Приводя неравенства к стандартному виду (≥0) и вводя добавочные переменныеy₁,y₂,y₃переходим к условиям-равенствам:

y₁=5x₁+x₂-2x₃+2

y₂=x₁-x₃-x₄+5 (2.5)

y₃=3x₁-5x₄+7

Число переменных (n = 7) на 4 превышает число уравнений (т = 3). Значит, четыре переменные могут быть выбраны в качестве свободных.

Пусть в качестве свободных  переменных выступаютx₁,x₂,x₃,x₄. Положим их равными нулю и получим опорное решение:

x₁=x₂=x₃=x₄=0;

y₁=2, y₂=5, y₃=7.

При этих значениях переменных Z= 0.

Это решение не оптимально, поскольку в линейной функции Z коэффициент приx₃отрицателен. Значит, увеличиваяx₃можно уменьшить Z.

Попробуем увеличиватьx₃.Из выражений (2.5) видно, что вy₁и y₂переменнаяx₃входит с отрицательным коэффициентом, значит, при увеличенииx₃соответствующие переменные могут стать отрицательными.

Определим, какая из этих переменных (y₁илиy₂)раньше обратится в нуль при увеличенииx₃Очевидно, что этоy₁она станет равной нулю приx₃=1, а величинаy₂— только приx₃= 5.

Выбирается переменная у, и вводится в число свободных  вместоx₃Чтобы разрешить систему (2.5) относительноx₃, y₂, y₃поступим следующим образом. Разрешим первое уравнение (2.5) относительно новой базисной переменнойx₃:

x₃=5/2*x₁+1/2*x₂-1/2*y₁+1

Это выражение подставляется  вместоx₃во второе уравнение:

x₃=5/2*x₁+1/2*x₂-1/2y₁+1;