Симплексный метод решения ЗЛП

 

Министерство образования  и науки Украины

Донбасская государственная  машиностроительная академия

Факультет автоматизации  машиностроения 
и информационных технологий

Кафедра интеллектуальных систем принятия решений

 

 

 

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

 

по дисциплине «МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ»

 

на тему

 

«Симплексный метод решения ЗЛП»

 

 

 

 

 

Выполнила

Студентка гр. ИС-09-1  __________________         ___________________

  подпись   Германенко М.А.

Руководители   __________________         ___________________

          подпись   Протыняк С. И.

                                 

                                                  __________________         ___________________

          подпись   Сташкевич И. И.

 

 

 

Краматорск 2011

 

 

реферат

 

Курсовая работа по дисциплине «Математические методы исследования операций» на тему: "Симплексный метод решения ЗЛП" студентки группы ИС 09–1 Германенко М.А. содержит 53 страницы машинописного текста, 4 рисунка, 4 таблицы, 19 страниц приложения.

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

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

 

МАТЕМАТИЧЕСКИЕ  МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ, ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ, ЭМЕРДЖЕНТНОСТЬ, СИМПЛЕКС-МЕТОД, ПРЯМАЯ ЗАДАЧА, ДВОЙСТВЕННАЯ ЗАДАЧА, УСЛОВИЕ НЕОТРИЦАТЕЛЬНОСТИ, ЦЕЛЕВАЯ ФУНКЦИЯ, БАЗИСНОЕ РЕШЕНИЕ, ПРОГРАММНЫЙ ПРОДУКТ.

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ…………………………………………………………………4

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

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

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

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

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

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

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

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

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

методом…………………………………………………………………...17

2.4 Двойственная  задача………………………………………………....23

ІІІ КОМПЬЮТЕРНАЯ РЕАЛИЗАЦИЯ СИМПЛЕКС-МЕТОДА ПРИ РЕШЕНИИ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ……….....28

3.1 Описание программного продукта……………………………...…28

3.2 Тестирование  программного продукта………………….…………30

ВЫВОДЫ………………………………………………………………….32

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ………………………….34

ПРИЛОЖЕНИЕ  А………………………………………………………...35

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

 

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

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

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

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

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

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

 

 

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

 

 

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=

,  X= ,   A₀=  (1.6)

 

Здесь:

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

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

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

Возьмем линейное неравенство 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. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.