Курсовая: Применение задачи линейного программирования для нахождения максимальной прибыли от реализации товара - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

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

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 261 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

38 Содержание Введение 3 Линейное программирование 5 Алгоритм симплекс-метода 19 Метод полного исключения Жордана 28 Экономическая постановка задачи 30 Автоматизация задачи с помощью Excel 33 Заключение 36 Список используемой литературы 38 Введение В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решений, в том числе и в финансовой математике. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов. В развитие и совершенствование этих систем вложен труд и талант многих математиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики. Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи: · рационального использования сырья и материалов; задачи оптимального раскроя; · оптимизации производственной программы предприятий; · оптимального размещения и концентрации производства; · составления оптимального плана перевозок, работы транспорта; · управления производственными запасами; · и многие другие, принадлежащие сфере оптимального планирования. Для большого количества практически интересных задач целевая функция выражается линейно – через характеристики плана, причем допустимые значения параметров подчинены линейным равенствам или неравенствам. Нахождение при данных условиях абсолютного экстремума целевой функции носит название линейного программирования. Первым исследованием по линейному программированию является работа Л. В. Кантфовича “Математические методы организации и планирования производства”, опубликованная в 1939 г. В нем дана постановка задач линейного программирования, разработан метод разрешающих множителей решения задач линейного программирования и дано его теоретическое обоснование. Прямая задача линейного программирования является математической формулировкой проблемы составления такого плана использования различных способов производства, который позволяет получить максимальное количество однородного продукта при имеющихся в наличии ресурсах. Математическое программирование – это прикладная отрасль математики, которая является теоретической основой решения задач оптимального планирования. Существуют следующие разделы математического программирования: линейное, параметрическое, нелинейное и динамическое программирование. Наиболее разработанным и широко применяемым разделом математического программирования является линейное программирование, целью которого служит отыскивание оптимума ( max , min )заданной линейной функции при наличии ограничений в виде линейных уравнений или неравенств. Линейное программирование Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Казалось бы, что для исследования линейной функции многих переменных на условный экстремум достаточно применить хорошо разработанные методы математического анализа, однако невозможность их использования можно довольно просто проиллюстрировать Основная теорема линейного программирования Целевая функция задачи линейного программирования достигает своего экстремума (минимума или максимума) в вершине допустимой области. Если целевая функция достигает экстремального значения более, чем на одной вершине, то она достигает того же значения в любой точке, являющейся выпуклой комбинацией этих вершин. Доказательство Обозначим вершины выпуклого многогранника через . Пусть для определенности мы ищем минимум . Пусть оптимальный план есть . Это означает, что для всех из допустимой области. Если - вершина, то первую часть теоремы можно считать доказанной. Пусть теперь - не вершина. Тогда её можно представить как выпуклую комбинацию вершин Поскольку - линейный функционал, то Обозначим через m минимум из всех значений , и пусть он достигается в вершине , т.е. Но тогда, так как , то С другой стороны, по определению оптимального плана, должно быть . Сравнивая, получим, что , то есть существует такая вершина , где целевая функция достигает того же минимального значения. Для доказательства второй части теоремы допустим, что принимает свое минимальное значение на нескольких вершинах сразу, например, на . Тогда Если - выпуклая комбинация этих вершин то принадлежит допустимой области и , что и доказывает теорему. Эта теорема имеет важнейшее значение, так как она указывает путь решения задачи линейного программирования. Совсем не надо перебирать все точки допустимой области. Достаточно перебрать вершины допустимой области, а ведь их - конечное число. Кроме того, как это окажется далее, не нужно перебирать все вершины , можно этот перебор существенно сократить. Только вот как узнать, имеем ли мы дело с вершиной или нет? Все дальнейшее изложение будет вестись для задач линейного программирования в канонической форме в векторных обозначениях Примеры моделей, приводящих к задачам линейного программирования Линейное программирование является одной из основных частей того раздела современной математики, который получил название математического программирования . В общей п остановке задачи этого раздела выглядят следующим образом. Имеются какие-то переменные и функция этих переменных , которая носит название целевой функции . Ставится задача: найти экстремум (максимум или минимум) целевой функции при условии, что переменные x принадлежат некоторой области G : В зависимости от вида функции и об ла сти G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Подробнее об этом будет сказано в заключении. Линейное программирование характеризуется тем, что а) функция является линейной функцией переменных ; б) область G определяется системой линейных равенств или неравенств Стандартная и каноническая формы задачи линейного программирования Обратите внимание на то, что в указанных выше двух примерах задачи имели достаточно разный вид: в задаче о диете требовалось найти минимум целевой функции, а в задаче о плане производства - максимум . В задаче о диете ограничения имели вид , а в задаче о плане производства - вид . Такой разнобой неудобен при разработке алгоритмов решения этих задач. Поэтому имеются некоторые стандартные формы задач линейного программирования , к которым и приводят различные конкретные задачи. Прежде чем выписывать эти формы, договоримся об обозначениях. Для более краткой записи мы будем использовать векторную или матричную запись. Под векторами мы будем понимать вектора-столбцы , например , , и т.д. Обозначение будет означать, что Соответственно, запись означает, что Первая стандартная форма задачи линейного программирования имеет вид (1.7) Введем вектора ; ; , a так ж е вектора , и матрицу . Заметим, что комбинация есть не что иное, как скалярное произведение векторов и . Поэтому в векторной форме задача (1.7) примет вид (1.8) Можно использовать и матричные обозначения . Тогда комбинация есть произведение и задача (1.7) примет вид (1.9) Вторая стандартная форма задачи линейного программирования имеет вид (1.10) В векторной форме эта задача имеет вид (1.11) и в матричной форме - вид (1.12) Канонической формой задачи линейного программирования называется задача вида (1.13) В векторной форме эта задача имеет вид (1.14) и в матричной форме - вид ( 1.15) Во всех этих задачах функцию называют целевой функцией . Вектор называют вектором коэффициентов линейной формы, вектор - вектором ограничений . Матрицу называют матрицей коэффициентов . Любой набор чисел , удовлетворяющий ограничениям задачи, называют планом , а множество всех планов - допустимой областью . Тот план, который доставляет экстремум (минимум или максимум) целевой функции, называют оптимальным планом или просто решением задачи линейного программирования. Правила приведения задач линейного программирования к стандартной и канонической формам Рассмотрим теперь те приёмы, которые позволяют произвольные формы задач линейного программирования приводить к указанным выше стандартным формам. 1. Превращение max в min и наоборот. Если целевая функция в задаче линейного программирования задана в виде , то, умножая её на (- 1), приведем её к виду , так как смена знака приводит к смене на . Аналогично мож н о заменить на . 2. Смена знака неравенства. Если ограничение задано в виде , то, умножая на (- 1), получим: . Аналогично, неравенство вида больше либо равно можно превратить в неравенство вида меньше либо равно. 3. Превращение равенства в систему неравенств. Если ограничение задано в виде , то его можно заменить эквивалентной системой двух неравенств , , или такой же системой неравенств со знаками больше либо равно . Указанные выше приемы позволяют приводить задачи линейного программирования к стандартной форме . 4. Превращение неравенств в равенства. Пусть исходная форма задачи линейного программирования имеет вид (1.16) Здесь первые r ограничений имеют вид неравенств со знаком меньше либо равно затем идет группа неравенств со знаком больше либо равно и, наконец, группа ограничений со знаком = . Для приведения задачи к канонической форме, где все ограничения имеют вид равенств , вводят дополнительные переменные , которые тоже считаются неотрицательными и записывают исходную задачу в виде (1.17 ) , т.е. в неравенстве со знаком меньше либо равно добавляют дополнительную неотрицательную переменную, а из неравенства со знаком больше либо равно вычитают дополнительную переменную. В целевую функцию эти дополнительные переменные включают с коэффициентом 0, т.е. фактически они в целевой функции отсутствуют. Получив решение задачи (1.17), т.е. решение задачи в канонической форме, для получения решения исходной задачи (1.16) надо просто выбросить из решения значения введенных дополнительных переменных. Пример Привести к каноническому виду задачу Введем дополнительные переменные . Переводя max в min, запишем задачу в виде что и дает эквивалентную задачу в канонической форме. 5. Ограничения на неотрицательность переменных. Во всех приведенных выше формах требуется, чтобы все переменные были неотрицательны, т.е. .В реальных задачах часто на переменные накладываются ограничение вида (они называются двусторонними ограничениями), или же условие неотрицательности какой-то переменной может отсутствовать вообще. Рассмотрим, как поступать в этих случаях. а) Пусть на переменную вообще не наложено никаких ограничений. Для приведения задачи к канонической форме введем две новые переменные и и будем считать, что После этого, заменив в исходной задаче на мы получим задачу линейного программирования в канонической форме. б) Пусть на наложено двустороннее ограничение вида .Введем переменную . Тогда будет , что дает ограничения в стандартной форме. Вводя дополнительную неотрицательную переменную , можно записать двустороннее ограничение в виде (1.18) После того, как в исходных соотношениях вместо будет подставлено выражение и добавлено ограничение, задача приобретет канонический вид Алгоритм симплекс-метода Симплекс метод – является универсальным методам, которым можно решить любую задачу линейного программирования. Сформулировать алгоритм симплекс-метода для решения задач линейного программирования, заданных в канонической форме . Обычно он реализуется в виде симплекс-таблицы. В первом столбце этой таблицы располагаются обозначения векторов, входящих в базис. Второй столбец - коэффициенты целевой функции, соответствующие векторам, входящим в базис. Третий столбец - компоненты опорного плана. В дополнительной строке в этом столбце пишется величина . Её легко вычислить перемножая числа из второго столбца и третьего столбца и складывая их. Далее идут столбцы, соответствующие всем векторам , и в этих столбцах записываются координаты этих векторов в рассматриваемом базисе. Заметим, что для векторов, входящих в базис, эти координаты имеют вид (0,0, ... ,0,1,0, ..., 0), где единица стоит в той строке, где находится сам этот базисный вектор. В дополнительной строке сверху обычно выписывают коэффициенты , соответствующие этим векторам. В дополнительной строке снизу пишутся величины , вычисляемые по формулам: . Заметим, что для векторов, входящих в базис, эти разности всегда равны нулю. Далее идут следующие этапы, связанные с преобразованием этой таблицы. При ручном счете каждый раз эту таблицу лучше переписывать заново, при счете на ЭВМ (который, естественно, всегда используется при решении практических, а не учебных задач), эта таблица просто преобразуется в памяти ЭВМ. Этап 1 Просматривается дополнительная строка снизу, где записаны разности . Если все эти разности , то план является оптимальным Этап 2 Если есть столбцы, где , то выбирается столбец с максимальным значением этой разности. Индекс j определит вектор, вводимый в базис. Пусть , то есть в базис надо вводить вектор . Назовем столбец, соответствующий этому вектору, направляющим столбцом . В дальнейшем мы будем направляющий столбец помечать символом . Этап 3 Просматривается столбец, соответствующий этому вектору. Если все , то значения целевой функции неограничены снизу . Если есть , то находятся где просматриваются лишь те дроби ,для которых Пусть этот минимум достигается для вектора . Тогда именно вектор подлежит выводу из базиса. Строка, соответствующая этому вектору, называется направляющей строкой . В дальнейшем в примерах мы будем помечать ее символом . Этап 4 После того, как определены направляющие столбец и строка, начинает заполняться новая симплекс-таблица, в которой на месте направляющей строки будет стоять вектор . Обычно заполнение этой новой таблицы начинается именно с направляющей строки. В качестве компоненты опорного плана туда пишется величина , то есть . Остальные элементы этой строки заполняются величинами . Обратите внимание на особую роль элемента , стоящего на пересечении направляющей строки и направляющего столбца. Именно на него делятся все бывшие элементы направляющей строки. На месте бывшего элемента автоматически появляется единица. Написанные выше формулы для пересчета элементов направляющей строки можно записать следующим правилом: . Этап 5 Далее начинается пересчет всех остальных строк таблицы, включая и дополнительную нижнюю строку по формулам: для компонент плана ; для координат разложения по базису ; для дополнительной строки . Обратите внимание на то, что все эти формулы по сути дела строятся по одному правилу . Это правило применимо и к компонентам плана, и к величинам , и к разностям . Его даже можно использовать для пересчета элементов самого направляющего столбца, хотя проще заполнить его нулями, оставив 1 на месте бывшего элемента . Далее итерации продолжаются. Пример Решить задачу линейного программирования В данном случае вектор равен (0,1,-3,0,2,0), а в векторной форме ограничения могут быть записаны в виде . Заполним исходную симплекс-таблицу, взяв в качестве исходного базиса вектора ,что удобно из-за их вида. Исходная симплекс-таблица Ба- План 0 1 -3 0 2 0 зис 0 7 1 3 -1 0 2 0 0 12 0 -2 4 1 0 0 0 10 0 -4 3 0 8 1 0 0 -1 3 0 -2 0 Обратите внимание на то, что из-за специфического вида векторов в столбец "план" просто переписался вектор , а в качестве координат векторов в нашем базисе стоят просто сами векторы. Ну, а величины приходится считать: Первая итерация Просматривая дополнительную строку мы видим, что в ней всего один положительный элемент - в столбце, соответствующем вектору . Следовательно, этот вектор надо вводить в базис и этот столбец и будет направляющим столбцом. В этом направляющем столбце есть два положительных числа - 4 и 3. Поэтому нужно рассмотреть два частных и выбрать из них наименьшее. Так как и он достигается на векторе , то этот вектор подлежит выводу из базиса и соответствующая ему строка и будет направляющей строкой. Ба- План 0 1 -3 0 2 0 зис 0 10 1 0 2 0 -3 3 0 1 0 0 0 1 0 0 8 1 -9 0 0 -2 0 Заполним теперь новую симплекс-таблицу, следуя сформулированным выше правилам. Начинается заполнение, естественно, со второй строки (так как она была направляющей), а затем пересчитываются все остальные строки. Вторая итерация Просматривая дополнительную строку мы вновь видим в ней всего один положительный элемент это 1/2, стоящая в столбце вектора . Следовательно, этот вектор надо ввести в базис и этот столбец будет направляющим. В столбце, соответствующем вектору , всего один положительный элемент это 5/2, которая стоит в первой строке. Поэтому первая строка будет направляющей и вектор должен быть выведен из базиса. Ба- План 0 1 -3 0 2 0 зис 1 4 1 0 0 -3 5 0 1 0 0 1 0 0 10 1 -11 0 0 0 Запишем новую симплекс-таблицу, следуя сформулированным выше правилам. В получившейся таблице в дополнительной строке стоят лишь отрицательные числа и нули. Поэтому получившийся план является оптимальным. Итак, оптимальный план имеет вид то есть , а все остальные Ему соответствует значение целевой функции, равное -11. Метод полного исключения Жордана Имеется система т линейных алгебраических уравнений с п неизвестными, решение которой надо найти: Производят такие преобразования, в резуль тате которых в каждой строке и в каждом столбце матрицы системы линейных алгебра ических уравнений остаются по одному неиз вестному с коэффициентами, равными единице, т. е. фактически получают решение системы. Например, необходимо исключить переменную x s из всех строк за исключением i -й. Коэф фициент a is , стоящий перед переменной x s , называют генеральным элементом, i -ю строку и 5-й столбец— разрешающими. Прежде всего разрешающую строку делят на a is и она остается без изменения. Чтобы исключить переменную x s из первого уравнения, умножают разреша ющую строку на — a is и складывают с первой строкой. В результате получают первую строку с нулевым элементом на месте a is . Аналогично исключают x s в остальных строках. Получают эквивалентную запись системы алгебраических уравнений. В ней г-я строка имеет прежний вид, но все коэффициенты у нее поделены на a is ; 5-й столбец состоит из нулевых элементов (кроме единичного, стоящего в /-й строке). Остальные элементы матрицы системы и сто лбец свободных переменных пересчитывают по правилу прямоугольника. Например, новое значе ние элемента а новое значение элемента столбца свободных членов Из правила прямоугольника следует, что когда в разрешающей строке (столбце) есть нулевые элементы, то элементы столбцов (строк), пе ресекающих эти нулевые элементы, остаются без изменения. Экономическая постановка задачи В продаже двух изделий А и В участвуют 3 отдела магазина на продажу одного изделия А: первый отдел затрачивает 7 часов; Второй отдел 7 часов; третий отдел 8 часов. На продажу изделия В: первый отдел затратил 13 часов; второй отдел 8 часов; третий отдел 2 часа.На продажу обоих изделий: первый отдел затратил 363 часов; второй отдел 327 часов; третий отдел 429 часов. От реализации одного изделия А магазин получил доход 6уе, а от реализации изделия В получил 4уе. Сколько будет максимальный доход от реализации двух изделий Составим математическую модель задачи Тогда задача ЛП формируется следующим образом: найти максимум целевой функции F(х)=6х 1 + фх 2 ® max при ограничениях 7x 1 +13x 2 <363 7x 1 +8x 2 <327 13x 1 +2x 2 <429 Приведем задачу к каноническому виду, для чего добавим в правые части ограничений дополнительные неизвестные х 3 , х 4 , х 5 (балансовые переменные) при ограничениях 7x+13x 2 +x 3 <363 7x 1 +8x 2 + +x 4 <327 13x 1 +2x 2 + +x 5 <429 Теперь составим симплексную таблицу 1-ого шага: Б.П С/Ч , b i -х 1 -х 2 -х 3 -х 4 -х 5 К , ci х 3 363 7 13 1 0 0 384 х 4 327 7 8 0 1 0 343 х 5 429 8 2 0 0 1 440 f(x) 0 -6 -4 0 0 0 10 b 1 =363*7-327*7/7=252/7 b 2 =327/7=327/7 b 3 = 327*8-429*7/7=387/7 a 12 =7*8-7*13/7=5 a 22 = 8/7=8/7 a 32 = 7*2-8*8/7=-50/7 a 14 =7*1-7*0/7=-1 a 24 =1/7=1/7 a 34 = 7*0-8*1/7=-8/ 7 c 1 = 7*343-7*384/7=287/7 c 2 = 343/7=343/7 c 3 = 7*440-8*343/7=336/7 БП С/Ч -х 1 -х 2 -х 3 -х 4 -х 5 К х 3 252/7 0 5 1 -1 0 287/7 х 4 327/7 1 8/7 0 1/7 0 343/7 х 5 387/7 0 -501/7 0 -817 1 336/7 f(x) 1962/7 0 20/7 0 6/7 0 1988/7 F(х)=327/7 * 6=1962/7 Автоматизация задачи с помощью Excel Теперь можно приступить к решению задачи на компьютере: 1. откроем новый рабочий лист (Вставка
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
- Николай, вы заняты? Нет? Ну славно! Приходите к нам, мы тут Бродского читаем! Алексей принёс четыре тома собрания сочинений. С нами две аспирантки филологического факультета МГУ и студентка консерватории. Если не трудно, захватите с собою какой-нибудь инструмент помузицировать - скрипку, а лучше виолончель.
- Серый, где ты таких находишь?! Чо такое виолончель? Литруха водяры, что ли?
- Да-да, Николай, мы ждём вас!
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru