МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО  ПО ОБРАЗОВАНИЮ

ТИХООКЕАНСКИЙ ГОСУДАРСТВЕННЫЙ

ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ

 

 

Кафедра математики и моделирования

Экономический институт

 

Специальность 080801 «Прикладная информатика в  экономике»

 

 

 

 

 

 

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

 

По дисциплине: Математические методы в экономике

 

На тему: Задача линейного программирования (симплекс-метод)

 

 

 

 

 

 

 

 

 

     Владивосток

2010

 

Содержание:

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

1. Теоретическая часть

     1.1 Линейное программирование …..3

     1.2 Табличный симплекс-метод …..4

2. Вычислительная процедура симплекс-метода

      2.1 Нахождение исходного опорного решения общей задачи линейного программирования (I часть симплекса )……………………………………………5

2.2 Переход от найденного опорного решения к лучшему опорному решению (II часть симплекса)……………………………………………………...7

2.3 Метод искусственного  базиса……………………………………………....9

3. Программная реализация

     3.1. Блок-схема алгоритма ЗЛП …12

     3.2. Описание основных процедур и функций …13

     3.3 Листинг программы…………………………………………………………15

4. Контрольный пример …26

5.Руководство пользователя……………………………………………………….29

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

Список использованной литературы …32

 

Введение

 

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

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

 

1. Теоретическая часть

1.1 Линейное программирование

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

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

где    - функция, описывающая ограничения,

* - один из  следующих знаков  ,

- действительное число, i= 1, …, m.

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

Задача линейного программирования может быть сформулирована в следующем  виде:

Найти max , при условии:

В случае, если все  ограничения заданы в виде строгих  неравенств, то данная форма называется канонической.

Так как min f(x) эквивалентен max [-f(x)], то задачу линейного программирования всегда можно свести к задаче максимизации.

Для решения задач линейного программирования существует множество методов:

1. графический;
2. табличный (прямой, простой) симплекс – метод;
3. метод искусственного базиса;
4. модифицированный симплекс-метод.

Рассмотрим один из них.

1.2 Табличный симплекс-метод

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

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

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

2.  Вычислительная процедура  симплекс - метода

2.1 Нахождение исходного опорного решения общей задачи линейного программирования (I часть симплекса )

Основу вычислительной схемы симплексного метода составляет метод Жордана - Гаусса.

Имеются два условия, по которым  можно судить, найдено опорное  решение или нет:

1 условие. Каждое уравнение системы ограничений должно быть разрешено относительно какой-либо переменной, то есть система ограничений должна быть приведена к единичному базису.

2 условие. Базисные переменные должны принимать только положительные значения.

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

1 этап. По условию задачи составляется её математическая модель.

2 этап. Составленная модель приводится к каноническому виду, это делается путём введения балансовых переменных, которые считаются всегда положительными. Они вводятся только в ограничения - неравенства, чтобы обратить их в уравнения, и входят в целевую функцию с нулевыми коэффициентами.

3 этап. Приведение системы к единичному базису с помощью метода Жордана - Гаусса. После выполнения 3 этапа первое условие опорного решения будет выполнено.

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

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

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

5 этап. Приведение преобразованной системы к единичному базису. Для этого используют метод Жордана - Гаусса, но ведущий элемент берется не произвольно, а по следующему правилу, которое гарантирует, что правые части не изменят своих положительных знаков.

Правило выбора ведущего элемента.

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

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

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

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

3. Ведущий элемент берётся на пересечении ведущего столбца и ведущей строки.

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

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

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