Реферат

Реферат Задач линейного программирования

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 8.11.2024



Цель работы: изучить теорию и методы решения задач линейного программирования; пробрести навыки построения моделей линейного программирования и решения задач линейного программирования на ЭВМ.

Краткие теоретические сведения

Методы линейного программирования (ЛП) оказались весьма эф

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

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

Пример 1. Фирма производит две модели и В) сборных книжных полок. Их производство ограничено наличием сырья (высоко

качественных досок) и временем машинной обработки. Для каждого из

делия модели А требуется 3 м2 досок, а для изделия модели В - 4 м2. Фирма может получить от своих поставщиков до 1 700 м2 досок в неде

лю. Для каждого изделия модели А требуется 12 мин машинного време

ни, а для изделия модели 5-30 мин. В неделю можно использовать 160 ч машинного времени.

Сколько изделий каждой модели следует фирме выпускать в не

делю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В-А дол. прибыли?

Чтобы сформулировать эту задачу математически, обозначим че

рез х{ количество выпущенных за неделю полок модели Л, а через х2 -количество выпущенных полок модели В. Задача состоит в том, чтобы найти наилучшие значения х\ и х2. Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют еженедель

ную прибыль. Еженедельная прибыль составляет

Р = 2x1, + 4x2.

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

х{ > 0, х2>0 (1)

Теперь ограничения на наличие досок и машинное время могут быть записаны следующим образом: для досок -

Зх1 + 4х2 < 1700 (2)

для машинного времени -

2X1 + 5 х2 < 1600. (3)

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

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

функцией своих переменных. Ограничения на эти переменные тоже линейны (1).


Рис. 1 Линия уровня целевой функции и допустимое множество задачи ЛП
Условия неотрицательности позволяют ограничиться рассмотре

нием положительного квадранта. Границы определяются прямыми

3x1 + 4х2 = 1700,

1 + 5х2 = 1 600.

Стрелка на каждой границе указывает, с какой стороны прямой * выполняется ограничение. Заштрихованная область ОАВС, содержащая точки, для которых соблюдены условия (2) и (3), является допустимой. Точки внутри и на границе этой области изображают допустимые решения. Допустимых решений много. Задача состоит в том, чтобы най

ти точку максимума функции Р.

Штриховыми линиями изображены прямые

2x1 + 4x2 =0,

2x1 + 4x2 = 800,

обозначенные а и b соответственно. Эти прямые параллельны и пред

ставляют собой две линии уровня функции Р со значениями 0 и 800. Яс

но, что значение функции Р возрастает по мере того, как линии уровня удаляются от начала координат в положительном квадранте.

ми (2, 4), указывающий направление возрастания функции Р перпенди

кулярен штриховым линиям и направлен в сторону, противоположную началу координат.

Линией уровня с наибольшим значением функции Р имеющей хотя бы одну точку с допустимой областью, является прямая с, прохо

дящая через вершину В; на ней Р принимает значение 1 400. Точка В, в которой х1 = 300, х2 = 200, соответствует оптимальному решению зада

чи. Эти значения могут быть получены как решения уравнений.



1 +4х2 =1700,

1 +5х2 =1 600.

Следовательно, максимальная прибыль составляет 2*300 + 4*200 = 1400.

В точке максимума оба ограничения превращаются в равенства, что означает полное использование сырья и машинного времени.

Пример 1 показывает, как возникают задачи линейного програм

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

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

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



Порядок выполнения работы

Вариант № 2

-2х1 + 3х2max

Графический метод:


х1 + 2х2 ≤ 12

1 + 2х2≥ 8

-2х1 + х2 ≥-8

1) х1 + 2х2 ≤12 2) 3х1 + 2х2 ≥8

х1 > 0 x2 > 0 х1 > 0 x2 > 0

x1 = 0 x2 = 6 x1 = 0 x2 = 4

x1 = 12 x2 = 0 x1 = 8/3 x2 = 0

3) -2х1 + х2 ≥-8

х1 > 0 x2 > 0

x1 = 0 x2 =-8

x1 = 4 x2 = 0

Таблица 1 – Начальное базисное решение

Базисные переменные

Переменные

Постоянные

х1

х2

х3

х4

х5




х3



















х4



















х5



















с - строка




















Опорная точка: х1 = 0, х2 = 0, х3 = 12, х4 = 8, х5 = -8, G = 0.

Таблица 2 – Правило минимальных отношений

№ строки

Базисные переменные

Отношение

1







2







3








Таблица 3 – Сложное базисное решение

Базисные переменные

Переменные

Постоянные

х1

х2

х3

х4

х5




x3











x4















x2















с - строка

















1. Реферат на тему Операция шунтирования коронарных артерий
2. Реферат Увольнение работников по инициативе работодателя
3. Реферат на тему Untitled Essay Research Paper Swift
4. Реферат на тему Untitled Essay Research Paper Gun Control New
5. Реферат Морской круиз
6. Контрольная работа Проблемы бытия в ХХ веке 2
7. Реферат на тему AZ Report On Russian Essay Research Paper
8. Реферат Физиология высшей нервной деятельности 2
9. Реферат Консолидированная отчетность и особенности ее анализа
10. Курсовая на тему Особенности развития благотворительности в Алтайском крае