(5 оценок, среднее: 4,80 из 5)
Загрузка...
Учебная работа. Курсовая работа: Задача линейного программирования
ФГОУ ПО (то есть программное обеспечение — комплект программ для компьютеров и вычислительных устройств) “ПСКОВСКИЙ КОЛЛЕДЖ СТРОИТЕЛЬСТВА И экономики”
Предмет “Математические способы”
Задачка линейного программирования
Курсовая работа
Студента группы 315-ПО (то есть программное обеспечение — комплект программ для компьютеров и вычислительных устройств)
Андреева Дмитрия Александровича
Управляющий курсовой работы
Васильева Наталья Анатольевна
Псков 2009 г.
Содержание
Введение
Глава Ι Линейное программирование
§ 1 Общая постановка задачки линейного программирования
§ 2 Математическая модель задачки линейного программирования
§ 3 Каноническая форма задачки линейного программирования
Глава ΙΙ Решение задачки симплексным способом
§ 1 Постановка задачки
§ 2 Составление математической модели задачки
§ 3 методы решения задачки симплексным способом
§ 4 Построение исходного опорного решения способом Гаусса
§ 5 Решение задачки
§ 6 Вывод
Заключение
Литература
Введение
В истинное время огромное количество задач планирования и управления в отраслях народного хозяйства, также большенный объём личных прикладных задач решаются способами математического программирования. Более развитыми в области решения оптимизационных задач являются способы линейного программирования. Эти способы разрешают обрисовать с достаточной точностью широкого круга задач коммерческой деятель, таковых, как планирование товарооборота; размещение розничной торговой сети городка; планирование товароснабжения городка, района; прикрепление торговых компаний к поставщикам; организация оптимальных перевозок продуктов; распределение работников торговли должностям; организация оптимальных закупок товаров питания; распределение ресурсов; планирование финансовложений; оптимизация межотраслевых связей; подмена торгового оборудования; определение рационального ассортимента продуктов в критериях ограниченной площади; установление оптимального режима работы.
В задачках линейного программирования аспект эффективности и функции в системе ограничений линейны.
Если содержательный смысл просит получения решения в целых числах, то таковая задачка является задачей целочисленного программирования.
Если в задачке математического программирования имеется переменная времени, а аспект эффективности выражается через уравнения, описывающие течение операций во времени, то таковая задачка является задачей динамического программирования.
В почти всех экономических моделях зависимости меж неизменными и переменными факторами можно считать линейными.
Внедрение способов математического программирования в коммерческой деятель соединено со сбором нужной инфы коммерсантом, экономистом, финансистом, потом постановкой задачки вкупе с арифметикой. Так как способы математического программирования уже реализованы на компе в виде пакета обычных программ, то доступ к ним обычно прост, автоматизирован и не составляет особенных проблем.
Тогда эксплуатация модели содержит в себе сбор и обработку инфы, ввод обработанной инфы в ЭВМ (Электронная вычислительная машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач), расчеты на базе разработанных программ календарных планов и, в конце концов, выдачу результатов вычислений (в комфортном для юзеров виде) для их использования в сфере производственной деятель.
Глава Ι Линейное программирование
§ 1 Общая постановка задачки линейного программирования
Линейное программирование – это направление математического программирование изучающая способы решения экстремальных задач, которые характеризуются линейной зависимостью меж переменными и линейной мотивированной функцией. Для решения задач линейного программирования составляется математическая модель задачки и выбирается способ решения.
Постановка задачки коммерческой деятель быть может представлена в виде математической модели линейного программирования, если мотивированная функция быть может представлена в виде линейной формы, а связь с ограниченными ресурсами обрисовать средством линейных уравнений либо неравенств. Не считая того, вводится доп ограничение – значения переменных должны быть неотрицательны, так как они представляют такие величины, как товарооборот, время работы, издержки и остальные экономические характеристики.
Геометрическая интерпретация экономических задач даёт возможность наглядно представить, их структуру, выявить индивидуальности и открывает пути исследования наиболее сложных параметров. задачка линейного программирования с 2-мя переменными постоянно можно решить графически. Но уже в трёхмерном пространстве такое решение усложняется, а в местах, размерность которых наиболее трёх, графическое решение, совершенно говоря, нереально. Вариант 2-ух переменных не имеет особенного практического значения, но его рассмотрение проясняет характеристики задач линейного программирования, приводит к идее её решения, делает геометрически приятными методы решения и пути их практической реализации.
§ 2 Математическая модель задачки линейного программирования
Перед решением задачки составляем её математическую модель.
Математическая модель – это совокупа соотношений состоящие из линейной мотивированной функции и линейных ограничений на переменную.
Принцип составления математической модели.
1. Выбирают переменные задачки.
Переменными задачки именуются величины 
которые на сто процентов охарактеризовывают экономический процесс, описанный в задачки. Обычно записываются в виде вектора X = (
) Причём 
)
2. Составляют систему ограничения задачки.
Система ограничений – это совокупа уравнений и неравенств, которым удовлетворяют переменные задачки и которая следует из ограниченности экономических критерий задачки.
В общем виде система записывается в виде
3. Задают мотивированную функцию.
Мотивированная функция – это функция Z(X) которая охарактеризовывает свойство выполнения задачки, экстремум которой нужно отыскать. В общем виде мотивированная функция записывается Z(X) = 
(max, min)
т.о. математическая модель имеет вид отыскать переменные задачки 
удовлетворяющие системе ограничений:
и условию неотрицательности 
0 (j = 
), которая обеспечивает экстремум мотивированной функции Z(Y) = 
Допустимым решением задачки линейного программирования именуется хоть какой набор значений переменных удовлетворяющий системе ограничений и условной неотрицательности.
Огромное количество допустимых решений образует область допустимых решений задачки (ОДР).
Хорошим решением именуется допустимое решение задачки, при котором мотивированная функция добивается экстремума.
§ 3 Каноническая форма задачки линейного программирования
Математическая модель задачки обязана иметь каноническую форму.
Если система ограничения состоит лишь из уравнения и все переменные удовлетворяют условию неотрицательности, то задачка имеет каноническую форму.
Если в системе есть хотя бы одно неравенства либо какая–или переменная неограниченна условию неотрицательности, то задачка имеет обычную форму. Чтоб привести задачку к каноническому виду нужно:
перейти от неравенств к уравнению последующим образом: в левую часть неравенств вводим доп переменную с коэффициентом (+1) для неравенства (
) и (-1) для неравенства () доп переменные не наложены мотивированные неотрицательности, то её подменяют разностью 2-ух неотрицательных переменных, другими словами:
= 
– 
(
Вид канонической формы:
Глава ΙΙ Решение задачки симплексным способом
Симплексный способ – это способ поочередного улучшения плана (решения), более действенный и применяется для решения хоть какой задачки линейного программирования.
Заглавие способа от латинского simplecx – обычной т.к. из исходного область допустимых решений задачки имела простой вид. Идеи способа предложил русский математик Контарович Л.В. в 1939 году и потом эту идею развил и разработал Дж. Данциг в 1949 году.
Симплексный способ дозволяет за конечное число шагов или отыскать наилучшее решение или обосновать что его нет.
§ 1 Постановка задачки
На предприятии в процессе производства употребляется 3 вида станков Ι, ІΙ, ІΙІ. При всем этом расходуется сырьё, трудовые ресурсы, и учитываются затратные расходы.
Понятно, что для производства станка Ι – ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 10 ед. затратных расходов; станка ΙІ – ого вида 6 ед. сырья, 2 ед. трудовых ресурсов и 8 ед. затратных расходов; для станка ΙΙІ – ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 18 ед. затратных расходов; Предприятие имеет в наличии 420 ед. сырья, 120 ед. трудовых ресурсов и 250 ед. затратных ресурсов.
Прибыль от реализации станка І вида — 28 тыс. руб., ІΙ вида — 24 тыс. руб., ΙІΙ вида — 20 тыс. руб. Условия производства просит, чтоб трудовые ресурсы были применены на сто процентов, а затратные расходы могли быть не наименее имеющихся в наличии.
Составить план производства станков, обеспечивающих наивысшую Прибыль.
§ 2 Составление математической модели задачки
Записываем условие задачки в виде таблицы.
Таблица
Вид ресурса
Расход рес. на Создание ед. продукции
Припас ресурса
Ι
ІΙ
ІΙІ
сырьё
4
2
10
420
трудовые ресурсы
6
2
8
120
затратные расходы
4
2
18
250
Прибыль
28
24
20
max
1. Выбирают переменные задачки.
Пусть 
количество производимых станков 1-ого, 2-ого и 3-его вида, 
2. Составляем систему ограничения задачки
по условию задачки требуется, чтоб
трудовые ресурсы были применены на сто процентов означает, ставим символ (=), а затратные расходы могли быть не наименее имеющихся в наличии означает, ставим символ (
).
3. Задаём мотивированную функцию
Z(X) = 
Математическая модель имеет вид: отыскать план выпуска станков
X = (
),
удовлетворяющий системе ограничений задачки
и условию неотрицательности 
), при котором Прибыль будет наибольшей
Z(X) = 
§ 3 Методы решения задачки симплексным способом
Общая мысль симплексного способа (способа поочередного улучшения плана) для решения задачки линейного программирования состоит
1) умение отыскивать исходный опорный план;
2) наличие признака оптимальности опорного плана;
3) умение перебегает к нехудшему опорному плану.
метод:
1) Математическая модель задачки обязана иметь каноническую форму. В неприятном случаи её приводят к каноническому виду.
2) Находят изначальное опорное решение задачки. Им является вектор, состоящий из тех переменных, которые входят лишь в одно уравнение в системе ограничений. Если изначальное решение сходу не отыскать то употребляют способ Гаусса.
количество переменных решения равно количеству уравнений системы. Заполняют симплексную таблицу по системе ограничений и мотивированной функции.
Макет симплексной таблицы:
Б
…
…
…
…
…
…
…
…
…
…
…
…
…
…
1-ый столбец – коэффициенты в мотивированной функции при базовых переменных.
2-ой столбец – базовые переменные.
3-ий столбец – вольные члены.
Самая верхняя строчка – коэффициенты при мотивированной функции.
2-ая верхняя строчка – сами переменные, входящие в мотивированную функцию и в систему ограничений.
Основное поле симплекс способа – система коэффициентов из уравнения.
Крайняя строчка – служит для того, чтоб ответить на вопросец: “оптимален план либо нет ”.
Индексная строчка дозволяет нам судить о оптимальности плана.
3) Инспектируют опорное решение, на оптимальность, вычисляя коэффициенты индексной строчки по форме:
При решении задачки вероятны два варианта:
— При решении задачки на максимум:
а) все оценки 
следует, что решение наилучшее
б) хотя бы одна оценка 
и при соответственной переменной нет положительных коэффициентов, то задачка не имеет рационального решения m, k, мотивированная функция неограниченна в О.Д.Р.
в) хотя бы одна оценка и при соответственной переменной есть положительный коэффициент то данное решение можно сделать лучше, построив новое опорное решение на котором мотивированная функция будет больше.
— При решении задачки на минимум:
а) все оценки 
следует, что решение наилучшее
б) хотя бы одна оценка 
и при соответственной переменной нет положительных коэффициентов, то задачка не имеет рационального решения m, k, мотивированная функция неограниченна в О.Д.Р.
в) хотя бы одна оценка и при соответственной переменной есть положительный коэффициент то данное решение можно сделать лучше, построив новое опорное решение.
4) Новое опорное решение находится при помощи главного столбца, главный строчки и главного элемента.
Главный столбец показывает на переменную, которую нужно вывести из числа базовых для улучшения решения.
Главная строчка показывает на переменную, которую нужно вывести из числа базовых для улучшения решения.
Главный элемент нужен для частей новейшего опорного решения (для новейшей симплексной таблицы).
Их нахождения зависит от цели задачки.
— При решении задачки на максимум:
а) главный столбец – это столбец с отрицательной меньшей оценкой 
в индексной строке.
б) главная строчка – это строчка с минимальным отношением вольных членов к положительным коэффициентам главного столбца:
min 
= 
в) главный элемент – это число расположенное на пересечении главных столбца и строчки(не быть может равен нулю).
— При решении задач на минимум:
а) главный столбец – это столбец с положительной меньшей оценкой в индексной строке.
б) главная строчка – это строчка с большим отношением вольных членов к положительным коэффициентам главного столбца:
mах =
в) главный элемент – это число размещено на пересечении главных столбца и строчки.
5) Заполняют первую симплексную таблицу последующим образом:
а) главную строчку делят на главный элемент и записывают на том же месте в новейшей таблице.
б) заполняют базовые столбцы.
в) другие элементы пересчитывают по правилу “прямоугольника”:
НЭ = СТЭ – 
где НЭ – новейший элемент
СТЭ – элемент старенького плана
РЭ – разрешающей элемент
А и Б – элементы старенького плана
6) Ворачиваются ко второму шагу метода – проверка плана на оптимальность.
§ 4 Построение исходного опорного решения способом Гаусса
Приводим задачку к каноническому виду.
Z(X) = 
)
Z(X) = 
)
4 2 10 1 0 420
6 2 8 0 0 120 * (-1)
4 2 18 0 -1 250
28 24 20 0 0 0
4 2 10 1 0 420
-6 -2 -8 0 0 -120 + + 
4 2 18 0 -1 250
28 24 20 0 0 0
-2 0 2 1 0 420
6 2 8 0 0 120 *12
-2 0 10 0 -1 130
28 24 20 0 0 0
-2 0 2 1 0 300
72 24 96 0 0 1440 —
-2 0 10 0 -1 130
28 24 20 0 0 0
-2 0 2 1 0 300
72 24 96 0 0 1440 
-2 0 10 0 -1 130
-44 0 -76 0 0 -1440
-2 0 2 1 0 300 *5
3 1 4 0 0 60
-2 0 10 0 -1 130 * (-1)
-44 0 -76 0 0 -1440
-10 0 10 5 0 1500
3 1 4 0 0 60
2 0 -10 0 1 -130 +
-44 0 -76 0 0 -1440
-10 0 10 5 0 1500 
3 1 4 0 0 60
12 0 0 5 1 1370
-44 0 -76 0 0 -1440
-2 0 2 1 0 300 —
3 1 4 0 0 60
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-4,4 0 2 0 -1 26 *2
3 1 4 0 0 60
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-8,8 0 4 0 -2 52
3 1 4 0 0 60 —
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-8,8 0 4 0 -2 52 *19
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440
-167,2 0 76 0 -38 988
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-44 0 -76 0 0 -1440 +
-167,2 0 76 0 -38 988 
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-123,2 0 0 0 -38 -452
-2,2 0 1 0 -0,5 13
11,8 1 0 0 2 8
2,4 0 0 1 1 274
-123,2 0 0 0 -38 -452
§ 5 Решение задачки
Составляем симплексную таблицу
Симплексная таблица 1
Б
-452
-123,2
0
0
0
-38
0
13
-2,2
1
0
0
-0,5
0
8
11,8
1
0
0
2
0
274
2,4
0
0
1
1
452
123,2
0
0
0
38
т. к все 
> 0 решение наилучшее
Ответ: max Z(X) = 452 при X = (0; 8; 13)
§ 6 Вывод
Наибольшая Прибыль в размере 425 тыс. руб. быть может достигнута, если создавать 8 станков ІΙ вида, 13 станков ІΙІ вида и не создавать станки Ι вида.
При всем этом расходуется 146 ед. сырья, 120 ед. трудовых ресурсов и 250 ед. затратных расходов.
Заключение
Данная курсовая работа посвящена вопросцу о решении задачки линейного программирования способом поочередного улучшения плана, по другому симплекс – способ. Состоит из введения, 2-ух глав, заключения и перечня литературы.
В первой главе рассказывается о линейном программировании а именно, и о том, что такое общая постановка задачки линейного программирования, как составить математическую модель, также поведано о канонической форме задач линейного программирования.
2-ая глава работы посвящена практической части решения задачки. Строится математическая модель, решается задачка симплексным способом, также способом Гаусса.
]]>