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

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

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

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

 

 

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

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

 

Специальность 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 (к единичному базису), или установим противоречивость системы ограничений.

Все вычисления 5 этапа производятся - в таблице Гаусса.

6. этап. Записываем опорное решение.

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

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

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

Правило подсчета оценочной строки

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

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

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

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

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

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

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

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

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

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

Пример. Найти оптимальное решение задачи линейного программирования симплексным методом.

х₁, х₂≥0

Z(x)=2x₁+5x₂→max

Решение.

1 этап не нужен, так как модель уже есть.

2 этап. Приводим задачу к каноническому виду. Для этого в ограничения-неравенства вводим неотрицательные балансовые переменные х₃, х₄, х₅. Балансовые переменные входят в целевую функцию Z(x) с нулевыми коэффициентами, в результате получим:

x_j≥0,

Z(x)=2x₁+5x₂+0 x₃+0x₄+0 x₅→max

3-й  этап не нужен, т.к. балансовые переменные одновременно являются базисными.

4-й  этап не выполняем, т.к. все свободные члены положительны.

5-й  этап не нужен, т.к. не делали 4-й этап.

6-й  этап. Записываем начальное опорное решение:

_опор={0,0,40,31,50}.

II часть симплекса.

 

 

Нет отрицательной  оценки

 

По последней симплекс-таблице  записываем оптимальное решение. Для  этого базисные переменные, указанные  в первом столбце, приравниваем к  числам, стоящим в столбце «план». Все остальные переменные являются свободными, они приравниваются к  нулю. Окончательно оптимальное решение  имеет вид: ={5,7,0,0,11}, при этом максимальное значение целевой функции Z_max=45.

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

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

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

Исходная  задача

x_j≥0, ; b_i≥0,

Расширенная задача