Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Казалось бы, что для исследования линейной функции многих переменных на условный экстремум достаточно применить хорошо разработанные методы математического анализа, однако невозможность их использования можно довольно просто проиллюстрировать. Для решения задач линейного программирования потребовалось создание специальных методов. В данной курсовой работе будет рассмотрен геометрический метод решения задач линейного программирования. Геометрический метод применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно. Таким образом, целью данной курсовой работы является: Для этого были поставлены следующие задачи:. Линейное программирование — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование является частным случаем математического программирования. Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования. Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их. Он был предложен в середине х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации. Математическая формулировка задачи линейного программирования. Иногда на x i также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя ее во всех остальных равенствах и неравенствах а также в функции f. Такую задачу называют "основной" или "стандартной" в линейном программировании. Найти такие неотрицательные значения х 1 , х 2 , Запись с помощью знаков суммирования. Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее наибольшее значение линейной функции. В дальнейшем рассмотрено решение задач линейного программирования, связанных с нахождением минимального значения линейной функции. Там, где необходимо найти максимальное значение линейной функции, достаточно заменить на противоположный знак линейной функции и найти минимальное значение последней функции. Заменяя на противоположный знак полученного минимального значения, определяем максимальное значение исходной линейной функции. Кратко напомним некоторые фундаментальные определения и теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем как линейного, так и нелинейного программирования. Фундаментальным понятием линейной алгебры является линейное вещественное пространство. Под ним подразумевается множество некоторых элементов именуемых векторами или точками , для которых заданы операции сложения и умножения на вещественное число скаляр , причем элементы, являющиеся результатом выполнения операций, также в соответствии с определением должны принадлежать исходному пространству. Частными случаями линейных пространств являются вещественная прямая, плоскость, геометрическое трехмерное пространство. Система векторов линейного пространства а 1 а 2 , В противном случае систему а 1 , а 2 , Максимально возможное количество векторов, которые могут образовывать линейно независимую систему в данном линейном пространстве, называют размерностью пространства, а любую систему линейно независимых векторов в количестве, равном размерности, — базисом пространства. Любое подмножество данного линейного пространства, которое само обладает свойствами линейного пространства, называется линейным подпространством. Если фундаментальным свойством любого линейного пространства или подпространства является принадлежность ему нулевого вектора, то для аффинного множества это не всегда так. На плоскости примером подпространства является прямая, проходящая через начало координат, а аффинного множества — любая прямая на плоскости. Характеристическим свойством аффинного множества является принадлежность ему любой прямой, соединяющей две любые его точки. Размерность аффинного множества совпадает с размерностью того линейного подпространства, сдвигом которого оно получено. Если рассматривается некоторое линейное пространство R n , то принадлежащие ему аффинные множества размерности 1 называются прямыми, а размерности n-1 —гиперплоскостями. Так, обычная плоскость является гиперплоскостью для трехмерного геометрического пространства R 3 , а прямая — гиперплоскостью для плоскости R 2. Всякая гиперплоскость делит линейное пространство на два полупространства. Линейная комбинация векторов а 1 , а Множество, содержащее все возможные выпуклые комбинации точек некоторого множества М, называют выпуклой оболочкой данного множества. Можно показать, что выпуклая оболочка множества М является наименьшим выпуклым множеством, содержащим М. Выпуклая оболочка конечного множества точек называется выпуклым многогранником, а непустое пересечение конечного числа замкнутых полупространств — многогранным выпуклым множеством. В отличие от выпуклого многогранника последнее может быть неограниченным. Точка v выпуклого множества V называется его угловой крайней точкой, если она не является внутренней точкой ни для какого отрезка, концы которого принадлежат множеству V. Угловые точки выпуклого многогранника являются его вершинами, а сам он — выпуклой оболочкой своих вершин. Выпуклая оболочка конечного множества лучей, исходящих из одной точки, называется многогранным выпуклым конусом с вершиной в данной точке. Пусть нам задана задача линейного программирования в стандартной форме. Возьмём на плоскости декартову систему координат и каждой паре чисел x 1 ,x 2 поставим в соответствие точку на этой плоскости. Они из всей плоскости вырезают лишь её первую четверть см. Как Вы, конечно, знаете, это прямая линия. Строить её проще всего по двум точкам. Дальше через эти две точки можно по линейке провести прямую линию рисунок 2. Чтобы найти другую точку, можно взять любое отличное от нуля значениеx 1 и вычислить соответствующее ему значение x 2. Эта построенная прямая разбивает всю плоскость на две полуплоскости. Узнать, в какой полуплоскости, какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, то есть точка 0,0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых составляют решение данной системы. Совокупность этих точек называют многоугольником решений. Это может быть точка, отрезок, луч, замкнутый многоугольник, неограниченная многоугольная область. Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Если система ограничений совместна, то по аналогии с трехмерным пространством она образует общую часть n-мерного пространства, называемую многогранником решений, так как координаты каждой его точки являются решением. Таким образом, геометрически задача линейного программирования представляет собой отыскание такой точки многогранника решений, координаты которой доставляют линейной функции минимальное значение, причем допустимыми решениями служат все точки многогранника решений. Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Пусть задача линейного программирования задана в двумерном пространстве, т. Если в ЗЛП ограничения заданы в виде неравенств с двумя переменными, она может быть решена графически. Графический метод решения ЗЛП состоит из следующих этапов. Сначала на координатной плоскости x 1 Ox 2 строится допустимая многоугольная область область допустимых решений, область определения , соответствующая ограничениям:. Не приводя строгих доказательств, укажем те случаи, которые тут могут получится. Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника рис. Оставшаяся часть будет неограниченным выпуклым многоугольником. Наконец, возможен случай, когда неравенства 1. Таким образом, эта прямая проходит через точки 0,1 и -1,0. При , а при. Наконец, рассмотри м прямую. Обратим внимание на то, что получившаяся область имеет вид выпуклого многоугольника. Вернёмся теперь к исходной задаче линейного программирования. Что будет происходить с нашей прямой? Ограничения задачи вырезают на плоскости некоторый многоугольник. Это пересечение дает какие-то значения переменных х 1 ,х 2 , которые являются планами. Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться см. Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице 1. Нормы расхода сырья на одно изделие, кг. Составить такой план выпуска продукции, при котором прибыль предприятия от реализации продукции будет максимальной при условии, что изделие В надо выпустить не менее, чем изделия А. Обозначим через х 1 и х 2 количество единиц продукции соответственно А и В, запланированных к производству. Так как, потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:. Конечную цель решаемой задачи — получение максимальной прибыли при реализации продукции — выразим как функцию двух переменных х 1 и х 2. Суммарная прибыль А составит 30х 1 от реализации продукции А и 40х 2 от реализации продукции В, то есть: Далее рассмотрим условие неотрицательности переменных: Эти два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте т. Чтобы учесть оставшиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получится система уравнений прямых:. Итак, наша прямая проходит через две точки 0, 75 и 25;0. Аналогично найдём остальные точки и запишем их в таблицу 1. Заштрихованная область, изображённая на рисунке, является областью допустимых значений функции F. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:. Для изготовления двух видов продукции Р 1 и Р 2 используют три вида сырья: Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2. Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль. Обозначим через х 1 количество единиц продукции Р 1 , а через х 2 — количество единиц продукции Р 2. Тогда, учитывая количество единиц сырья, расходуемое на изготовление продукции, а так же запасы сырья, получим систему ограничений:. То же самое получаем и для продукции Р 2. Таким образом, на неизвестные х 1 и х 2 должно быть наложено ограничение неотрицательности: Реализация х 1 единиц продукции Р 1 и х 2 единиц продукции Р 2 дает соответственно 50х 1 и 40х 2 руб. Условиями не оговорена неделимость единица продукции, поэтому х 1 и х 2 план выпуска продукции могут быть и дробными числами. Построим в программе Excelтаблицы нахождения точек пересечения линий с осями координат Рисунок 1 и график Рисунок 2. Заштрихованная область, изображённая на рисунке, является областью допустимых значений функции Z. Имеется два вида корма. A и B, содержащие вещества витамины S 1 , S 2 , S 3. Содержание числа единиц питательных веществ в одном кг каждого вида корма и необходимый минимум самих питательных веществ даны в таблице:. Пусть х 1 и х 2 — количество кормоввида А и В соответственно. Так количество питательных веществ не должно быть меньше необходимого минимума, то запишем следующую систему неравенств:. Минимальную стоимость витаминов за 1 кг корма, выразим следующей функцией: Выделенная область, изображённая на рисунке, является областью допустимых значений функции F. Точка В - оптимальное решение. Трикотажная фабрика использует для производства свитеров и кофточек шерсть, силикон и нитрон, запасы которых составляют , и кг. Количество пряжи каждого вида в кг , необходимой для изготовления одного изделия, а также прибыль, получаемая от их реализации, приведены в таблице. Пусть х 1 и х 2 — норма расхода пряжи для свитеров и кофточек соответственно. Количество пряжи каждого вида в кг , необходимой для изготовления одного изделия запишем в следующую систему неравенств:. Максимальная прибыль от реализации свитеров и кофточек выразим следующей функцией: На звероферме могут выращиваться чёрно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используются три вида кормов. Определить, сколько лисиц и песцов следует выращивать на звероферме, чтобы прибыль от реализации их шкурок была максимальной. Пусть х 1 и х 2 — количество единиц корма, которые должны получать лисиа и песец, соответственно. Количество единиц каждого вида корма, необходимого для выращивания одного животного запишем в следующую систему неравенств:. Максимальная прибыль от реализации шкурок выразим следующей функцией: Точка С - оптимальное решение. В данной курсовой работе мною были освоены навыки решения задач линейного программирования геометрическим методом. Для этого я изучила теоретические сведения, необходимые для решения задач линейного программирования указанным методом. Я узнала, что данный метод применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Также я узнала, как строятся прямые на плоскости, для чего разобрала основные понятия линейной алгебры и выпуклого анализа. После чего, рассмотрела все этапы геометрического решения задач линейного программирования, благодаря чему я узнала, что бывают разные случаи при решении задач, а именно:. В первых двух случаях задача может иметь единственное решение в конкретной точке, а также в любой точке отрезка или луча. Таким образом, освоив все необходимые навыки использования геометрического метода для решения задач линейного программирования, я решила поставленные задачи. Авиация и космонавтика Административное право Арбитражный процесс 23 Архитектура Астрология 4 Астрономия Банковское дело Безопасность жизнедеятельности Биографии Биология Биология и химия Биржевое дело 68 Ботаника и сельское хоз-во Бухгалтерский учет и аудит Валютные отношения 50 Ветеринария 50 Военная кафедра ГДЗ 2 География Геодезия 30 Геология Геополитика 43 Государство и право Гражданское право и процесс Делопроизводство 19 Деньги и кредит ЕГЭ Естествознание 96 Журналистика ЗНО 54 Зоология 34 Издательское дело и полиграфия Инвестиции Иностранный язык Информатика Информатика, программирование Исторические личности История История техники Кибернетика 64 Коммуникации и связь Компьютерные науки 60 Косметология 17 Краеведение и этнография Краткое содержание произведений Криминалистика Криминология 48 Криптология 3 Кулинария Культура и искусство Культурология Литература: Плохо Средне Хорошо Отлично. Банк рефератов содержит более тысяч рефератов , курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: А также изложения, сочинения по литературе, отчеты по практике, топики по английскому. Решения задач линейного программирования геометрическим методом Название: Решения задач линейного программирования геометрическим методом Раздел: Рефераты по экономико-математическому моделированию Тип: Для этого были поставлены следующие задачи: Общая задача имеет несколько форм записи. Линейное пространство обычно обозначают как R n , где n — его размерность. Пусть нам задана задача линейного программирования в стандартной форме 1. Нормы расхода сырья на одно изделие, кг AB. Супер у Вас сайт! Сделай паузу, студент, вот повеселись: Виктора в группе звали Вием, потому что препод на лекции, когда тот привычно в наглую спал сидя на первом ряду столов, сказал одногруппникам: Кстати, анекдот взят с chatanekdotov. Где скачать еще рефератов? Кто еще хочет зарабатывать от рублей в день "Чистых Денег"? Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?
Сколько калорий в кочане капусты
Рисуем туман гуашью
Зао кфк тамп