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

2

2203 - Программное обеспечение автоматизированных систем и

вычислительной техники

КУРСОВАЯ РАБОТА

по дисциплине:

М а т е м а т и ч е с к и е м е т о д ы

Тема: «Методы линейного программирования»

2006

СОДЕРЖАНИЕ:

ВВЕДЕНИЕ…………………………………………………………………...3

1. Понятие линейного программирования……………………….…………6

2.Симплекс метод…………………………………………………………….7

3.Экономическая постановка задачи.…………………………….…….…....8

4. Понятие математической модели………….………………………….......9

5.Двойственная задача линейного программирования.…………..…….…11

6. Решение исходной задачи двойственным симплекс методом………...13

7.Решение задачи графическим методом………………………………......18

ЗАКЛЮЧЕНИЕ……………………………………………………………...20

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

Введение.

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

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

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

Модель задачи математического программирования включает:

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

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

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

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

Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Кан-торовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в эконо-мике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач -- симплекс-метод. Общая идея симплексного метода (ме-тода последовательного улучшения плана) для решения ЗЛП состоит в следующем:

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

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

умение переходить к нехудшему опорному плану.

1.Понятие линейного программирования.

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

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

2.Симплекс метод

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

3.Экономическая постановка задачи

Для откорма крупно рогатого скота используют два вида кормов: b1, b2, в которые питательные вещества а1,а2,а3,а4. Содержание количества единиц питательных веществ в 1 кг каждого корма, стоимость 1 кг корма и содержание питательных веществ в рационе животного представлены в таблице 7. Составьте рацион при условии минимальной стоимости.

Таблица 7

Питательные вещества	Виды кормов	Норма содержание питательных веществ
	b1	b2
а1	3	4	24
а2	1	2	18
а3	4	0	20
а4	0	1	6
Стоимость 1кг корма, руб	1	2

4.Понятие математической модели

Решение какой-либо задачи управления можно разбить на несколько этапов:

формулировка задачи;

разработка математической модели изучаемой системы;

выбор метода и отыскание решения с помощью этой модели;

проверка решения.

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

Итак, математическая модель означает перевод задачи на язык количественных терминов.

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

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

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

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

5.Двойственная задача линейного программирования

Каждой задаче линейного программирования можно поставить в соответствие другую задачу линейного программирования. Решая одну из

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

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

Количество переменных в двойственной задаче равно количеству неравенств в исходной.

Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

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

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

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

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

Теорема 1 (первая теорема двойственности)

Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*)=G(y*), где х*, у* - оптимальные решения задачи I и II

Теорема 2 (вторая теорема двойственности)

Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задачи I и II соответственно, хотя бы одно из любой пары сопряженных неравенств обращается в равенство.

6. Решение исходной задачи двойственным симплекс методом

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

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

Возможны ситуации:

В индексной F- строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятым с противоположным знаком. Переходим к IV этапу.

В индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных элементов. Тогда делаем вывод о том, что целевая функция F>? неограниченно убывает.

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

Имеем задачу (I) построим ей двойственную (II).

I. II.

F=2X₁+X₂min G=24Y₁ + 18Y₂ + 20Y₃ + 6Y ₄max

Приведем ее к каноническому виду.

Введем базисные переменные ,

G=- G = -24Y₁ - 18Y₂ - 20Y₃ - 6Y ₄ min

Решаем симплекс-методом задачу .

1.Найдем разрешающий элемент.

1.1. Из отрицательных элементов индексной F- строки выберем наибольший по модулю, назовем соответствующий ему столбец - разрешающим.

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

В нашем примере, (Таблица 1), элемент 3 - разрешающий. Строка, соответствующая этому элементу тоже называется разрешающей.

Таблица 1

базисные	-Y1	-Y2	-Y3	-Y 4	свободные
Y5	3	1	4	0	2
Y6	4	2	0	1	1
-G	-24	-18	-20	-6	0

2. Выбрав разрешающий элемент, делаем перечет таблицы по правилам:

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

Y ₅, которая выходит из базиса, и теперь свободная.

2.2. На месте разрешающего элемента записываем обратное ему число (Таблица 2).

2.3. Элементы разрешающей строки делятся на разрешающий элемент.

2.4. Элементы разрешающего столбца делятся на разрешающий элемент и записываются с противоположным знаком.

2.5. Чтобы заполнить оставшиеся элементы таблицы 5, осуществляем пересчет по правилу прямоугольника.

Пусть мы хотим посчитать элемент, стоящий на месте 2(Y₂;Y₆ )

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

Итак, . Записываем на место, где было 3(Таблица 2).

Пересчитываем так все элементы:

Таблица 2

базисные	Y5	Y2	Y3	Y 4	свободные
Y1				0
Y6				1
-G	8	-10	12	-6	16

Проверим целевую функцию, согласно условиям.

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

Таблица 3

базисные	-Y5	-Y1	-Y3	-Y 4	свободные
Y2	1	3	4	0	2
Y6	-2	-2		1	-3
-G	18	30	52	-6	36

Таблица 4

базисные	-Y5	-Y1	-Y3	-Y 6	свободные
Y2	1	3	4	0	2
Y4	-2	-2		1	-3
-G	6	18	16	6	54

В индексной F- строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятым с противоположным знаком. Переходим к IV этапу.

Выписываем решение согласно таблице 4:

Y₁= 0; Y₄=-3;

Y₂= 2; Y₅= 0;

Y₃ = 0; Y₆= 0;

Подставляем полученные решения в условия задачи:

I. II.

Два условия в II системе не совпадают, выписываем из в I системы эти условия и решаем как систему уравнений.

F=2X₁+X₂min = 2*6+6 = 18

Ответ к задаче:

Для эффективного откорма крупно рогатого скота необходимо 6 корма b1 и 6 корма b2 . При этом затраты минимальны и составят 18 руб.

7.Решение задачи графическим методом.

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

Рис. 6

Отобразим ограничения в математической модели на графике (Рис. 6):

1 - 4 -

2 - 5 -

3 - 6 - F - F=2X₁+X₂min

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

Параллельно двигаем прямую F, соответствующую целевой функции. Первой вершиной, через которую пройдет прямая, при выходе за границу многоугольника, будет вершина A(6;6)(Рис.6):. Именно в ней достигнет своего минимального значения.

=6;

=6;

Подставляем значения в формулу:

2*6+6=18.

Для эффективного откорма крупно рогатого скота необходимо 6 корма b1 и 6 корма b2 . При этом затраты минимальны и составят 18 руб.

ЗАКЛЮЧЕНИЕ

Данная курсовая работа включает в себя предмет: «математические методы».

В курсовой работе были рассмотрены следующие вопросы:

- Рассмотрен алгоритм симплекс метода.

- Рассмотрено решение задачи графическим способом.

- Решена задача симплекс методом.

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

Лищенко «Линейное и нелинейное программирование», 1987

А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», 1987