Курсовая работа: Векторное пространство Решение задач линейного программирования графическим способом
Название: Векторное пространство Решение задач линейного программирования графическим способом Раздел: Рефераты по математике Тип: курсовая работа | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
РЕФЕРАТ Курсовая работа: 25 с., 4 рис., 2 табл., 17 источников. ВЕКТОР, ЛИНЕЙНОЕ ПРОСТРАНСТВО, ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ГРАФИЧЕСКИЙ МЕТОД Объект исследования – математические методы в экономике. Предмет исследования – графический метод в решении задачи линейного программирования, его особенности и область применения. Цель работы : закрепить понятие векторного пространства, выявить методы линейного программирования, расширить знания в области применения графического метода в решении экономических задач. Методы исследования : классификации, описания, моделирования и экономико-математические. Исследования : на примере определенных экономических задач рассмотрен порядок их решения графическим способом и дана оценка данного метода. Область возможного практического применения : все экономические задачи, в которых возможно применение этого метода. Значимость : данный метод дает возможность наглядно представить структуру экономических задач, выявить их особенности и открывает пути исследования более сложных свойств. Автор работы подтверждает, что приведенный в ней материал правильно и объективно отражает состояние исследуемого метода, а все заимствованные из литературных и других источников теоретические, методологические и методические положения и концепции сопровождаются ссылками на их авторов. 1 Векторные пространства, их свойства и дополнительные структуры 2 Задача линейного программирования и этапы ее решения графическим методом 3 Решение экономических задач графическим способом Список использованной литературы Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие при ограниченности ресурсов и технологических возможностей. Поэтому все более и более исключительно важное значение приобретает использование математических методов и средств вычислительной техники при решении экономических задач. при современных масштабах производства даже незначительные ошибки оборачиваются громадными потерями. В связи с этим для студентов экономических ВУЗов необходимо как знание возможностей применения математических методов и электронно-вычислительных машин, так и понимание тех проблем, которые возникают при их использовании. Такие методы объединяются под общим названием – математическое программирование. Математическое программирование – область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных. Целью данной работы является определение задачи линейного программирования и их решение с помощью графического метода. Методы, которые были использованы при написании работы, - метод классификации, описания, моделирования и экономико-математические методы. Для достижения главных целей и задач курсовой работы использовались такие книги как «Высшая математика. Математическое программирование» А.В.Кузнецова, В.А.Саковича, Н.И.Холода, «Математическое программирование в примерах и задачах» А.И. Акулича, в которых рассматриваются задачи линейного, нелинейного и динамического программирования. Для определения понятия векторного пространства автор обращался к книге «Элементы линейной алгебры» Р.Ф.Апатенок, где излагаются все вопросы раздела «Линейная алгебра».Также для написания работы использовались учебные пособия и другая литература. 1 Векторные пространства , их свойства и дополнительные структуры Центральными понятиями линейной алгебры является вектор и векторное пространство. Рассмотрим некоторое множество Полем P будем называть множество действительных или комплексных чисел, т.е. Если каждой паре чисел x и y, принадлежащих множеству L, по некоторому правилу поставлен в соответствие элемент z из множества L, то говорят, что на множестве L определена внутренняя операция. Если для каждого элемента х, принадлежащего L, и любого числа Элементы множества L называют векторами, а элементы поля P — скалярами. Линейное или векторное пространство над полем Р – некоторое множество L, для которого определены внешняя и внутренняя операции и выполняются следующие условия: 1. 2. 3. Существует такой элемент 4. Для любого элемента 5. 6. 7. 8. Условия 1-8 справедливы Для того, чтобы лучше осознать сущность линейных пространств, приведем их примеры. Следующие множества с известными операциями сложения элементов и умножения элементов на вещественные числа являются линейными пространствами над полем вещественных чисел: а) множество вещественных чисел; б) множество геометрических векторов в трехмерном пространстве (линейное пространство в) множество векторов, параллельных некоторой плоскости (прямой); г) множество столбцов с д) множество Для каждого из указанных множеств выполняются восемь аксиом линейного пространства, причем нулевым элементом являются: число нуль для пространства а); нулевой вектор для пространств б) и в); столбец и Из определения линейного пространства вытекают следующие утверждения или свойства: 1) В линейном пространстве R существует единственный нулевой элемент. Предположим, что в линейном пространстве L существуют два нулевых вектора 2) Предположим, что для элемента С другой стороны,
Сравнивая результаты, имеем 3) Произведение числа 0 на любой элемент х есть нулевой элемент. Действительно,
4) С линейными пространствами в первую очередь связано понятие линейного подпространства – такое множество векторов из L, которое само является линейным пространством над полем P. Чтобы подмножество было подпространством, необходимо и достаточно, чтобы выполнялись 2 условия: 1. 2. Свойства подпространств: · Пересечение любого семейства подпространств — снова подпространство; · Сумма конечного семейства подпространств — снова подпространство. Дополнительными структурами векторного пространства являются нормированное векторное пространство, топологическое линейное пространство, евклидово пространство и гильбертово пространство. Векторное пространство, в котором определена норма, называется нормированным векторным пространством или просто нормированным пространством. Топологическое линейное пространство – линейное пространство наделённое топологией, относительно которой операции сложения и умножения на число непрерывны. Действительным евклидовым пространством или просто евклидовым пространством называется действительное линейное пространство, на элементах которого определено скалярное произведение. Гильбертово пространство — обобщение евклидова пространства, допускающее бесконечную размерность. Закончим этот раздел важнейшим понятием изоморфизма между двумя линейными пространствами U и V. Два линейных пространства U и V над одним и тем же полем P называются изоморфными, если между их элементами можно установить такое взаимно однозначное соответствие, при котором сумме векторов пространства U отвечает сумма соответствующих векторов V, а произведению числа на вектор пространства U отвечает произведение того же числа на соответствующий вектор пространства V. Таким образом, понятие линейного пространства относится к числу основных в математике. Абстрактное определение линейного пространства вводится следующим образом: непустое множество элементов любой природы называется линейным пространством, если для любых двух элементов 2 Задача линейного программирования и этапы ее решения графическим методом Векторные пространства широко используются не только в линейной алгебре. На множествах n-мерного векторного пространства решением экстремальных задач, задаваемых системами линейных уравнений и неравенств, занимается такая математическая дисциплина, как линейное программирование. Методы и модели линейного программирования широко применяются при оптимизации процессов в экономике. Это, например: задача об оптимальном использовании ресурсов при производственном планировании, задача о смесях (планирование состава продукции), задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке"), транспортные задачи (анализ размещения предприятия, перемещение грузов). Первая работа, в которой были разработаны методы линейного программирования, была написана в 1939 г. советским математиком-экономистом Л.В. Канторовичем и носила название «Математические методы организации и планирования производства». Именно ее появление открыло новый этап в применении математики в экономике. Через 10 лет американским математиком Дж. Данцингом был разработан важный и очень эффективный метод решения подобного типа задач – симплекс-метод. Сам же термин «линейное программирование» впервые появился в 1951 г. в работах Дж. Данцига и Т. Купманса. Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования, которое, кроме линейного, включает в себя целочисленное, динамическое, нелинейное, параметрическое программирование.Это объясняется тем, что математические модели большого числа экономических задач линейны относительно искомых переменных и некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования.К тому же данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, исозданы соответствующие программы для электронно-вычислительных машин. Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать,ограничения в виде системы линейных уравнений или неравенств,требование неотрицательности переменных. В общем виде модель записывается следующим образом: · целевая функция:
· ограничения: a11x1 + a12x2 + ... + a1nxn ≤ b1,a21x1 + a22x2 + ... + a2nxn ≤ b2, ... am1x1 + am2x2 + ... + amnxn ≤ bm;(1.2) · требование неотрицательности: xj ≥ 0, При этом aij, bi, cj ( Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3). Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми. Вектор Каноническая задача линейного программирования:
a11x1 + a12x2 + ... + a1nxn = b1, a21x1 + a22x2 + ... + a2nxn = b2, ... am1x1 + am2x2 + ... + amnxn = bm; xj ≥ 0, Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи. Далее приведем примеры некоторых типовых задач, решаемых при помощи методов линейного программирования. Такие задачи имеют реальное экономическое содержание. 1. Задача об оптимальном использовании ресурсов при производственномпланировании. Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида ( Далее приведем простой пример задачи такого класса. Компания специализируется на выпуске хоккейных клюшек и наборов шахмат . Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов. Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль? 2. Задача о смесях (планирование состава продукции). К группе задач о смесях относят задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Иными словами, получаемые смеси должны иметь в своем составе m различных компонентов в определенных количествах, а сами компоненты являются составными частями n исходных материалов. Пример задачи: На птицеферме употребляются два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II - 2 рубля. Составьте ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион. 3. Транспортная задача. Под транспортной задачей понимают целый ряд задач, имеющих определенную специфическую структуру. Наиболее простыми транспортными задачами являются задачи о перевозках некоторого продукта из пунктов отправления в пункты назначения при минимальных затратах на перевозку. Пример: Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно. Необходимо определить наиболее дешевый вариант перевозок, при этом каждый поставщик должен отправить столько груза, сколько имеется у него в запасе, а каждый потребитель должен получить нужное ему количество продукции. Геометрическая интерпретация экономических задач дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования более сложных свойств. Задачу линейного программирования с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах размерностью больше трех графическое решение практически невозможно. Таким образом, данный метод решения задачи линейного программирования имеет очень узкие рамки применения. Однако метод представляет большой интерес с точки зрения выработки наглядных представлений о сущности задач линейного программирования. Пусть дана задача Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (2.2), (2.3) задает на плоскости Выпуклое множество – множество, которое вместе с любыми своими точками Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений задачи линейного программирования – непустое множество, например многоугольник Выберем произвольное значение целевой функции
Рисунок 1 Для того, чтобы установить направления возрастания или убывания целевой функции, найдем частные производные целевой функции по Частная производная (2.4) (2.5) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, Вектор –с указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. Вектор Из геометрической интерпретации элементов задачи линейного программирования вытекает следующий порядок ее графического решения. 1. С учетом системы ограничений строим область допустимых решений. 2. Строим вектор 3. При решении задачи на максимум перемещаем линию уровня 4. Определяем оптимальный план Сделаем некоторые примечания: 1) Если область допустимых решений — пустое множество, то задача не имеет решения ввиду несовместности системы ограничений. 2) Если область допустимых решений неограничена по направлению вектора Для обоснования методов решения задач линейного программирования сформулируем ряд важнейших теорем, уяснить смысл каждой из которыхнам поможет приведенное выше понятие о геометрической интерпретации решения задача линейного программирования. Теорема 1 . Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым. В частном случае, когда в систему ограничений входят только две переменные x1 и x2, это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x1, x2 ≥ 0), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой. Теорема 2 . Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений. Из теоремы 2 можно сделать вывод о том, что единственность оптимального решения может нарушаться, причем, если решение не единственное, то таких оптимальных решений будет бесчисленное множество (все точки отрезка, соединяющего соответствующие угловые точки). Теорема 3 . Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений, и наоборот. Следствием из теорем 2 и 3 является утверждение о том, что оптимальное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допустимым базисным решением (допустимыми базисными решениями) системы ограничений, следовательно оптимальное решение задачи линейного программирования следует искать среди конечного числа допустимых базисных решений. Таким образом, линейное программирование – раздел математического, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. Для решения задач линейного программирования потребовалось создание специальных методов. Особенно широкое распространение линейное программирование получило в экономике, так как исследование зависимостей между величинами, встречающимися во многих экономических задачах, приводит к линейной функции с линейными ограничениями, наложенными на неизвестные. 3 Решение экономических задач графическим способом Теперь рассмотрим несколько задач линейного программирования и их решение графическим методом. Задача 1. maxZ = 1+
Решение. Заметим, что полуплоскости, определяемые системой неравенств данной задачи не имеют общих точек (рисунок 2 [14, с. 31, рисунок 3.4]). Задача не имеет решения по причине несовместности условий задачи.
Рисунок 2 Задача 2.Цех выпускает два вида продукции, используя два вида полуфабрикатов. Продукция используется при комплектовании изделий, при этом на каждую единицу продукции первого вида требуется не более двух единиц продукции второго вида. Нормы расхода Решение. Пусть х =
( maxZ =10 Ограничения на полуфабрикаты:
6 Условие комплектности и неотрицательности переменных: 2
Таблица 1
Построив соответствующие данным ограничениям-неравенствам граничные прямые
Рисунок 3 Поскольку Решая совместно уравнения граничных прямых АВ и ОА, находим координаты точки А: Итак, по оптимальному плану следует выпускать 160 ед. продукции Графическим методом можно решить задачу линейного программирования с n>2 переменными, если в ее канонической записи число неизвестных n и число линейно независимых уравнений mсвязаны соотношением n-m≤2. В этом случае каноническую форму задачи преобразовывают в симметричную, которая будет содержать не более двух переменных. Решая эту задачу графически, находят два компонента оптимального плана. Подставляя их в ограничения задачи, определяют и остальные компоненты. Задача 3. Двум погрузчикам разной мощности за 24 часа нужно погрузить на первой площадке 230 т., на второй 168 т. Первый погрузчик на первой площадке может погрузить 10 т. в час, на второй – 12 т. Второй – на каждой площадке может погрузить по 13 т. в час. Стоимость работ, связанных с погрузкой 1 т. первым погрузчиком на первой площадке составляет 8 р., на второй площадке – 7 р. Стоимость погрузки вторым погрузчиком на первой площадке составляет 12 р., на второй – 13 р. Нужно составить план работы, т.е. найти, какой объем работ должен выполнить каждый погрузчик на каждой площадке, чтобы стоимость всех работ по погрузке была минимальной, учитывая, что по техническим причинам первый погрузчик на второй площадке должен работать не более 16 часов. Решение. Обозначим через Т аблица 2
Построим математическую модель задачи. Целевая функция описывает затраты, связанные с выполнением всех работ: 8 Ограничения на лимиты рабочего времени: Необходимость выполнить задание: Условие неотрицательности: Исключим из модели переменные min Z = 4944 - 4 Очевидно, что целевая функция Z = 4944 - 4 max Графическое решение задачи представлено на рисунке 4 [13, с. 36, рисунок 1.6].
Рисунок 4 Функция Из выражений для Итак, по оптимальному плану первый погрузчик должен погрузить 100 т. на первой площадке и 168 т. на второй, второму погрузчику надлежит погрузить 130 т. на первой площадке. Стоимость всех работ составит 3536 р. ( Таким образом, процедура поиска решения в таких простейших задачах линейного программирования является несложной: нужно каким-либо способом описать многоугольник допустимых точек, найти его вершины и выбрать из них те, координаты которых придают максимальное значение целевой функции. Кроме того, заслуживает рассмотрения и наглядная связь между нормалью к линейной форме, задающей целевую функцию, и нормалями к прямым, пересечение которых определяет решение задачи. И хотя в случае, когда изучаются задачи линейного программирования в пространстве большого числа переменных с большим числом ограничений, структура допустимого множества становится гораздо менее наглядной, а вычислительные сложности возрастают чрезвычайно, основные идеи поиска решения остаются неизменными. В любом из современных курсов экономики в той или иной степени используется математический аппарат: анализируются графики различных зависимостей, проводится математическая обработка статистических данных и т.д. В эпоху рыночных отношений роль математических методов многократно возросла. Так как главная проблема экономики – проблема рационального выбора, то чтобы его сделать становится необходимым произвести математический расчет или построить математическую модель.В большом числе случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Геометрическая интерпретация экономических задач дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования более сложных свойств. Задачу линейного программирования с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах размерностью больше трех графическое решение практически невозможно. Таким образом, данный метод решения задачи линейного программирования имеет очень узкие рамки применения. Однако метод представляет большой интерес с точки зрения выработки наглядных представлений о сущности задач линейного программирования. Список использованной литературы 1. Акулич, И.Л. Математическое программирование в примерах и задачах / И.Л. Акулич. – Минск: «Вышэйшая школа», 1986. – 319 с. 2. Александров, П. С. Курс аналитической геометрии и линейной алгебры / П.С. Александров. – Москва: «Наука»,1979. - 512 с. 3. Апатенок, Р.Ф. Элементы линейной алгебры / Р.Ф. Апатенок. – Минск: «Вышэйшая школа», 1977. – 256 с. 4. Ашманов, С.А. Линейное программирование / С.А. Ашманов. – Москва: «Наука», 1981. – 340 с. 5. Банди, Б. Основы линейного программирования: Пер. с англ / Б. Банди. – Москва: «Радио и связь», 1989. - 176 с. 6. Булдырев, В.С. Линейная алгебра и функции многих переменных / В.С. Булдырев, Б.С. Павлов. – Ленинград: Издательство Ленинградского университета, 1985. - 496 с. 7. Бутузов, В.Ф. Линейная алгебра в вопросах и задачах / В.Ф. Бутузов, Н.Ч. Крутицкая, А.А. Шишкин. – Москва: ФИЗМАТЛИТ, 2002. — 248 с. 8. Васильев, Ф.П. Линейное программирование / Ф.П. Васильев, А.Ю. Иваницкий. – Москва: «Факториал», 1998. – 176 с. 9. Головина, Л.И. Линейная алгебра и некоторые ее приложения / Л.И. Головина. – Москва: «Наука»,1975. - 408 с. 10. Замков, О.О. Математические методы в экономике / О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемных. – Москва: «Дело и Сервис», 2001. – 368 с. 11. Конюх, А.В. Высшая математика: практикум: в 2 ч. / А.В. Конюх, О.Н. Поддубная, С.В. Майоровская. – Минск: БГЭУ, 2008. – Ч. 1. – 253с. 12. Конюховский, П.В. Математические методы исследования операций в экономике / П.В. Конюховский. – Санкт-Петербург: «Питер», 2000. – 207 с. 13. Кузнецов, А.В. Высшая математика. Математическое программирование / А.В. Кузнецов, А.В. Сакович, Н.И. Холод. – Минск: «Вышэйшая школа», 1994. – 286 с. 14. Лунгу, К.Н. Линейное программирование. Руководство к решению задач / К.Н. Лунгу. – Москва: ФИЗМАТЛИТ, 2005. – 128 с. 15. Малугин, В.А. Математика для экономистов: Линейная алгебра. Курс лекций / В.А. Малугин. – Москва: «Эксмо», 2006. – 224 с. 16. Солодовников, А.С. Системы линейных неравенств / А.С. Солодовников. – Москва: «Наука», 1977. – 112 с. 17. Солодовников, А.С. Математика в экономике / А.С. Солодовников, А.В. Бабайцев, А.В. Браилов. – Москва: «Финансы и статистика», 2000. – 224 с. |