главнаяреклама на сайтезаработоксотрудничество Библиотека Revolution
 
 
Сколько стоит заказать работу?   Искать с помощью Google и Яндекса
 



Векторное пространство. Решение задач линейного программирования графическим способом

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

Рубрика: Математика
Вид: курсовая работа
Язык: русский
Дата добавления: 14.11.2010
Размер файла: 1,2 M

Полная информация о работе Полная информация о работе
Скачать работу можно здесь Скачать работу можно здесь

рекомендуем


Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже.

Название работы:
E-mail (не обязательно):
Ваше имя или ник:
Файл:


Cтуденты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны

Подобные работы


1. Теория информации. Статистический подход
Статистический подход к измерению правовой информации. Графический метод решения задач линейного программирования. Методика решения задач линейного программирования графическим методом. Количество информации как мера неопределенности состояния системы.
контрольная работа [79,4 K], добавлена 04.06.2010

2. Симплекс метод в форме презентации
Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлена 30.11.2010

3. Линейные пространства
Понятие и характеристика линейного пространства, его главные свойства и особенности. Исследование аксиом векторного пространства. Анализ отличий и признаков векторного подпространства. Базис и формулы линейного пространств, определение его размерности.
реферат [249,4 K], добавлена 21.01.2011

4. Методы оптимизации
Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа [517,9 K], добавлена 30.04.2011

5. Метод Гомори
Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
курсовая работа [67,5 K], добавлена 25.11.2011

6. Последовательность решения задач линейного программирования симплекс-методом
Обыкновенные и модифицированные жордановы исключения. Последовательность решения задач линейного программирования симплекс-методом применительно к задаче максимизации: составлении опорного плана решения, различные преобразования в симплекс-таблице.
курсовая работа [37,2 K], добавлена 01.05.2011

7. Решение задач линейного программирования симплекс методом
Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
курсовая работа [197,1 K], добавлена 09.04.2013

8. Задачи математического программирования
Понятие и виды задач математического линейного и нелинейного программирования. Динамическое программирование, решение задачи средствами табличного процессора Excel. Задачи динамического программирования о выборе оптимального распределения инвестиций.
курсовая работа [126,5 K], добавлена 21.05.2010

9. Методы решения задач математического моделирования
Основные понятия математического моделирования, характеристика этапов создания моделей задач планирования производства и транспортных задач; аналитический и программный подходы к их решению. Симплекс-метод решения задач линейного программирования.
курсовая работа [2,2 M], добавлена 11.12.2011

10. Векторы, пространства, гиперплоскости, гиперповерхности
Системы линейных уравнений и интерпретация их решений как пересечение гиперплоскостей в n-мерном координатном пространстве. Размерность и подпространства линейного пространства. Оптимизационные задачи линейного программирования. Суть симплекс-метода.
курсовая работа [132,2 K], добавлена 10.01.2014


Другие документы, подобные Векторное пространство. Решение задач линейного программирования графическим способом


РЕФЕРАТ

Курсовая работа: 25 с., 4 рис., 2 табл., 17 источников.

ВЕКТОР, ЛИНЕЙНОЕ ПРОСТРАНСТВО, ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ГРАФИЧЕСКИЙ МЕТОД

Объект исследования - математические методы в экономике.

Предмет исследования - графический метод в решении задачи линейного программирования, его особенности и область применения.

Цель работы: закрепить понятие векторного пространства, выявить методы линейного программирования, расширить знания в области применения графического метода в решении экономических задач.

Методы исследования: классификации, описания, моделирования и экономико-математические.

Исследования: на примере определенных экономических задач рассмотрен порядок их решения графическим способом и дана оценка данного метода.

Область возможного практического применения: все экономические задачи, в которых возможно применение этого метода.

Значимость: данный метод дает возможность наглядно представить структуру экономических задач, выявить их особенности и открывает пути исследования более сложных свойств.

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

Содержание

  • Введение
  • 1 Векторные пространства, их свойства и дополнительные структуры
  • 2 Задача линейного программирования и этапы ее решения графическим методом
  • 3 Решение экономических задач графическим способом
  • Заключение
  • Список использованной литературы

Введение

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

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

Целью данной работы является определение задачи линейного программирования и их решение с помощью графического метода.

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

Для достижения главных целей и задач курсовой работы использовались такие книги как «Высшая математика. Математическое программирование» А.В.Кузнецова, В.А.Саковича, Н.И.Холода, «Математическое программирование в примерах и задачах» А.И. Акулича, в которых рассматриваются задачи линейного, нелинейного и динамического программирования. Для определения понятия векторного пространства автор обращался к книге «Элементы линейной алгебры» Р.Ф.Апатенок, где излагаются все вопросы раздела «Линейная алгебра». Также для написания работы использовались учебные пособия и другая литература.

1 Векторные пространства, их свойства и дополнительные структуры

Центральными понятиями линейной алгебры является вектор и векторное пространство.

Рассмотрим некоторое множество и будем говорить, что над элементами этого множества определены внутренняя и внешняя операции.

Полем P будем называть множество действительных или комплексных чисел, т.е. или .

Если каждой паре чисел x и y, принадлежащих множеству L, по некоторому правилу поставлен в соответствие элемент z из множества L, то говорят, что на множестве L определена внутренняя операция.

Если для каждого элемента х, принадлежащего L, и любого числа из поля Р поставлен в соответствие элемент у из множества L, то будем говорить, что задана внешняя операция.

Элементы множества L называют векторами, а элементы поля P -- скалярами.

Линейное или векторное пространство над полем Р - некоторое множество L, для которого определены внешняя и внутренняя операции и выполняются следующие условия:

1. (коммутативность сложения);

2. (ассоциативность сложения);

3. Существует такой элемент , что (существование нейтрального элемента относительно сложения);

4. Для любого элемента существует такой элемент , что х + = (существование противоположного элемента);

5. (ассоциативность умножения на скаляр);

6. (умножение на нейтральный элемент поля P сохраняет вектор);

7. (дистрибутивность умножения на вектор относительно сложения скаляров);

8. (дистрибутивность умножения на скаляр относительно сложения векторов).

Условия 1-8 справедливы L и Р.

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

а) множество вещественных чисел;

б) множество геометрических векторов в трехмерном пространстве (линейное пространство );

в) множество векторов, параллельных некоторой плоскости (прямой);

г) множество столбцов с элементами (линейное пространство );

д) множество -матриц с вещественными элементами (линейное пространство ).

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

Из определения линейного пространства вытекают следующие утверждения или свойства:

1) В линейном пространстве R существует единственный нулевой элемент.

Предположим, что в линейном пространстве L существуют два нулевых вектора и . Тогда + = , так как -- нулевой элемент и + = , так как -- нулевой элемент. Сравнивая эти равенства и учитывая условие 1, получим = [3, с.103].

2) R существует единственный противоположный элемент x', выражающийся формулой .

Предположим, что для элемента имеются два противоположных ему элемента и . Тогда

С другой стороны,

Сравнивая результаты, имеем [3, с.103].

3) Произведение числа 0 на любой элемент х есть нулевой элемент.

Действительно,

[3, с.104].

4) .

С линейными пространствами в первую очередь связано понятие линейного подпространства - такое множество векторов из L, которое само является линейным пространством над полем P. Чтобы подмножество было подпространством, необходимо и достаточно, чтобы выполнялись 2 условия:

1. ;

2. .

Свойства подпространств:

· Пересечение любого семейства подпространств -- снова подпространство;

· Сумма конечного семейства подпространств -- снова подпространство.

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

Векторное пространство, в котором определена норма, называется нормированным векторным пространством или просто нормированным пространством.

Топологическое линейное пространство - линейное пространство наделённое топологией, относительно которой операции сложения и умножения на число непрерывны.

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

Гильбертово пространство -- обобщение евклидова пространства, допускающее бесконечную размерность.

Закончим этот раздел важнейшим понятием изоморфизма между двумя линейными пространствами U и V. Два линейных пространства U и V над одним и тем же полем P называются изоморфными, если между их элементами можно установить такое взаимно однозначное соответствие, при котором сумме векторов пространства U отвечает сумма соответствующих векторов V, а произведению числа на вектор пространства U отвечает произведение того же числа на соответствующий вектор пространства V.

Таким образом, понятие линейного пространства относится к числу основных в математике. Абстрактное определение линейного пространства вводится следующим образом: непустое множество элементов любой природы называется линейным пространством, если для любых двух элементов L однозначно определен третий элемент z L, называемый их суммой и обозначаемый x + y , и для каждого числа и любого элемента x L определен элемент x L так, что введенные операции сложения и умножения на число удовлетворяют условиям существования линейного пространства. Часто элементы абстрактных линейных пространств называют векторами, а само пространство векторным. Так, линейные пространства могут быть образованы не только лишь арифметическими векторами - эти пространства могут быть построены из объектов самой различной природы, что отличает математику от других наук.

2 Задача линейного программирования и этапы ее решения графическим методом

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

Первая работа, в которой были разработаны методы линейного программирования, была написана в 1939 г. советским математиком-экономистом Л.В. Канторовичем и носила название «Математические методы организации и планирования производства». Именно ее появление открыло новый этап в применении математики в экономике. Через 10 лет американским математиком Дж. Данцингом был разработан важный и очень эффективный метод решения подобного типа задач - симплекс-метод. Сам же термин «линейное программирование» впервые появился в 1951 г. в работах Дж. Данцига и Т. Купманса.

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

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

В общем виде модель записывается следующим образом:

· целевая функция:

= c1x1 + c2x2 + ... + cnxn > max(min); (1.1)

· ограничения:

a11x1 + a12x2 + ... + a1nxn ? b1, a21x1 + a22x2 + ... + a2nxn ? b2,

...

am1x1 + am2x2 + ... + amnxn ? bm; (1.2)

· требование неотрицательности:

xj ? 0, (1.3)

При этом aij, bi, cj (, ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3).

Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми.

Вектор , удовлетворяющий ограничениям (1.2) и (1.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (1.1) достигает своего максимального (минимального) значения, называется оптимальным.

Каноническая задача линейного программирования:

= c1x1 + c2x2 + ... + cnxn > max(min);

a11x1 + a12x2 + ... + a1nxn = b1,

a21x1 + a22x2 + ... + a2nxn = b2,

...

am1x1 + am2x2 + ... + amnxn = bm;

xj ? 0,

Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.

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

1. Задача об оптимальном использовании ресурсов при производственном планировании.

Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (, ). Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, bi и cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль преприятия была бы наибольшей.

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

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $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.1) - (1.3) есть выпуклое множество.

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

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений задачи линейного программирования - непустое множество, например многоугольник (рисунок 1 [2, с. 29, рисунок 1.3] ).

Выберем произвольное значение целевой функции . Получим . Это уравнение прямой линии. В точках NM целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (2.1) Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня функции (линиями постоянного значения).

Рисунок 1

Для того, чтобы установить направления возрастания или убывания целевой функции, найдем частные производные целевой функции по и :

Частная производная (2.4) (2.5) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, и скорости возрастания Z соответственно градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор -с указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор перпендикулярен к прямым Z = const семейства .

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

1. С учетом системы ограничений строим область допустимых решений.

2. Строим вектор наискорейшего возрастания целевой функции - вектор градиентного направления.

3. При решении задачи на максимум перемещаем линию уровня перемещают в антиградиентном направлении (на рисунке 1 - до точки ).

4. Определяем оптимальный план и экстремальное значение целевой функции .

Сделаем некоторые примечания:

1) Если область допустимых решений -- пустое множество, то задача не имеет решения ввиду несовместности системы ограничений.

2) Если область допустимых решений неограничена по направлению вектора , то сама целевая функция неограничена сверху в этой области, и тогда max Z = . Если область допустимых решений неограничена в направлении, противоположном c, то получаем min Z= .

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

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

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

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

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

Следствием из теорем 2 и 3 является утверждение о том, что оптимальное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допустимым базисным решением (допустимыми базисными решениями) системы ограничений, следовательно оптимальное решение задачи линейного программирования следует искать среди конечного числа допустимых базисных решений.

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

3 Решение экономических задач графическим способом

Теперь рассмотрим несколько задач линейного программирования и их решение графическим методом.

Задача 1.

max Z = 1+ - ,

.

Решение. Заметим, что полуплоскости, определяемые системой неравенств данной задачи не имеют общих точек (рисунок 2 [14, с. 31, рисунок 3.4]). Задача не имеет решения по причине несовместности условий задачи.

Рисунок 2

Задача 2. Цех выпускает два вида продукции, используя два вида полуфабрикатов. Продукция используется при комплектовании изделий, при этом на каждую единицу продукции первого вида требуется не более двух единиц продукции второго вида. Нормы расхода полуфабрикатов каждого вида на единицу выпускаемой продукции, общие объёмы полуфабрикатов и прибыль от единицы каждой продукции представлены в таблице 1[13, с. 32, таблица 1.3]. Определить план производства, доставляющий максимум прибыли.

Решение. Пусть х = () - план задачи. Тогда модель задачи примет вид

max Z =10+35

Ограничения на полуфабрикаты:

+2?800,

6+2?2400

Условие комплектности и неотрицательности переменных:

2?

?0, ?0.

Таблица 1

Полуфабрикаты

Нормы затрат на единицу продукции

Объём полуфабриката

I

II

1

6

2

2

800

2400

Прибыль

10

35

Построив соответствующие данным ограничениям-неравенствам граничные прямые +2=800, 6+2=2400, 2-=0, определим полуплоскости, в которых выполняются эти неравенства (рисунок 3 [13, с. 32, рисунок 1.5]). Для этого достаточно взять произвольную точку, не лежащую на граничной прямой, и подставить её координаты в неравенство. Для первых двух неравенств возьмём, например, начало координат О(0; 0). Получим истинные утверждения (0?800, 0?2400). Следовательно, первые два неравенства выполняются в полуплоскостях, содержащих точку О. Граничная прямая, соответствующая третьему неравенству, проходит через начало координат. Значит, нужно взять, например, точку (0; 10). Получаем ложное утверждение (0?10). Следовательно, третьему неравенству удовлетворяют точки полуплоскости, не содержащей пробной точки (0; 10).

Рисунок 3

Поскольку ?0 и ?0, областью допустимых решений является четырёхугольник ОАВС. Далее надо построить вектор с = (). Так как он необходим лишь для выяснения направления возрастания целевой функции, иногда для большей наглядности удобно строить вектор лс (). В нашем примере взято л=10 и построен вектор проводим линию уровня Z=0. Параллельным перемещением прямой Z=0 находим точку А, в которой целевая функция достигает максимума.

Решая совместно уравнения граничных прямых АВ и ОА, находим координаты точки А: =160, =320. При этом = max Z = z (A) =12800.

Итак, по оптимальному плану следует выпускать 160 ед. продукции и 320 ед.продукции , что принесёт прибыль в 12800 р.

Графическим методом можно решить задачу линейного программирования с n>2 переменными, если в ее канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением n-m?2. В этом случае каноническую форму задачи преобразовывают в симметричную, которая будет содержать не более двух переменных. Решая эту задачу графически, находят два компонента оптимального плана. Подставляя их в ограничения задачи, определяют и остальные компоненты.

Задача 3. Двум погрузчикам разной мощности за 24 часа нужно погрузить на первой площадке 230 т., на второй 168 т. Первый погрузчик на первой площадке может погрузить 10 т. в час, на второй - 12 т. Второй - на каждой площадке может погрузить по 13 т. в час. Стоимость работ, связанных с погрузкой 1 т. первым погрузчиком на первой площадке составляет 8 р., на второй площадке - 7 р. Стоимость погрузки вторым погрузчиком на первой площадке составляет 12 р., на второй - 13 р. Нужно составить план работы, т.е. найти, какой объем работ должен выполнить каждый погрузчик на каждой площадке, чтобы стоимость всех работ по погрузке была минимальной, учитывая, что по техническим причинам первый погрузчик на второй площадке должен работать не более 16 часов.

Решение. Обозначим через объем работ (в тоннах) i-го погрузчика (i=1,2) на j-ой площадке (j=1,2). Условия задачи перенесем в таблицу 2 [13, с. 34, таблица 1.4].

Таблица 2

i j

Лист рабочего времени

I погрузчик

10

8

12

7

24

II погрузчик

13

12

13

13

24

Задание

230

168

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

8+7+12+13

Ограничения на лимиты рабочего времени:

Необходимость выполнить задание:

Условие неотрицательности:

Исключим из модели переменные и . Из ограничений неравенств имеем = 230 - , = 168 - . Подставив выражения для и в ограничения неравенства и целевую функцию, получим задачу линейного программирования с двумя переменными .

min Z = 4944 - 4- 6,

Очевидно, что целевая функция Z = 4944 - 4- 6 достигает минимального значения при условии, что принимает максимальное значение. Имеем задачу

max

Графическое решение задачи представлено на рисунке 4 [13, с. 36, рисунок 1.6].

Рисунок 4

Функция достигает наибольшего значения при

Из выражений для и получим 0.

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

... читать дальше >>>

Поcмотреть текст работы Поcмотреть полный текст
Скачать работу можно здесь Скачать работу "Векторное пространство. Решение задач линейного программирования графическим способом" можно здесь
Сколько стоит?

Рекомендуем!

база знанийглобальная сеть рефератов