Автор: Пользователь скрыл имя, 25 Октября 2013 в 18:25, курсовая работа
Задача оптимизации может быть сформулирована на языке математики, если множество доступных вариантов удается описать с помощью математических соотношений (равенств, неравенств, уравнений), а каждое решение – оценить количественно с помощью некоторого показателя, называемого критерием оптимальности или целевой функцией. Тогда наилучшим решением будет то, которое доставляет целевой функции наибольшее или наименьшее значение, в зависимости от содержательного смысла задачи.
Введение 3
1 Линейное программирование 4
1.1 Задачи линейного программирования 4
1.2 Решение задач линейного программирования симплекс – методом 5
1.3 Решение задач линейного программирования графическим методом 10
2 Реализация методов линейного программирования на практическом применении 11
2.1 Пример решения задачи линейного программирования симплекс-методом 11
2.2 Пример решения задачи линейного программирования графическим способом 14
2.3 Пример решения задачи линейного программирования с помощью MS EXCEL 16
3 Решение задач линейного программирования 20
3.1 Решение задачи линейного программирования графическим методом 20
3.2 Решение задачи линейного программирования симплекс-методом 27
3.3 Решение транспортной задачи 31
Заключение 36
Список использованной литературы 37
в) выбор разрешающего элемента: элемент, стоящий на пересечении разрешающих строки и столбца. Пусть это будет элемент .
г) переменную вводим в базис вместо переменной .
д) элементы новой симплекс-таблицы пересчитываем по следующим формулам:
разрешающий элемент ,
элементы разрешающего столбца ,
элементы разрешающей строки ,
остальные элементы симплекс-таблицы по правилу прямоугольника:
1.3 Решение задач линейного
программирования графическим
Алгоритм решения:
2 Реализация методов линейного программирования на практическом применении
2.1 Решение задачи линейного
программирования Симплекс-
Трикотажная фабрика использует для производства свитеров и кофт чистую шерсть, силон и нитрон, запасы, которых составляют 606, 802 и 840 кг. На изготовление свитера расходуется 9 кг шерсти, 15 кг силона и 15 кг нитрона. На изготовление кофты расходуется 27 кг шерсти, 15 кг силона и 3 кг нитрона. От реализации одного свитера фабрика имеет прибыль 11 у. е., а от одной кофты прибыль составляет 6 у. е. Определить максимальную прибыль от реализации всей продукции производства свитеров и кофт.
Таблица 1.
Сорт материала |
Свитер |
Кофта |
Запасы сырья |
Шерсть |
9 |
27 |
606 |
Силон |
15 |
15 |
802 |
Нитрон |
15 |
3 |
840 |
Прибыль (у. е.) |
11 |
6 |
0 |
Математическая постановка задачи
Общая модель:
P1 и P2 – виды продукции: свитера и кофты.
s1, s2, s3 – запасы сырья: шерсть, силон, нитрон.
α – прибыль от реализации
единицы готовой продукции
β – прибыль от реализации
единицы готовой продукции
Решение задачи
1. Составим математическую
Пусть х1 – единица готовой продукции вида P1,
x2 – единица готовой продукции вида P2,
Цель фабрики получить максимальную прибыль от реализации всей продукции видов P1 и P2, тогда:
F=11x1 +6x2 → max
Система ограничений:
9x1 + 27x2 ≤ 606
15x1 + 15x2 ≤ 802
15x1 + 3x2 ≤ 840
x1 ≥ 0, x2 ≥ 0 условие неотрицательности.
F=11x1 +6x2 → max
9x1 + 27x2+x3= 606
15x1 + 15x2 +x4= 802
15x1 + 3x2+x5 = 840
x1 ≥ 0, x2 ≥ 0, x3≥0, x4≥0, x5≥0
x3=606 – 9x1 - 27x2
x4=802 – 15x1 - 15x2
x5=840 – 15x1 - 3x2
Таблица 2.
Своб. перем. Базис. перем. |
-x1 |
-x2 |
Свободные члены |
Симплексные отношения |
x3 |
9 |
27 |
606 |
≈-0,75 |
x4 |
15 |
15 |
802 |
≈0,030 |
x5 |
15 |
3 |
840 |
≈-0,090 |
F-строка |
-11 |
-6 |
0 |
Начальный план не оптимален, так как в F-строке есть отрицательные элементы.
Таблица 3.
Своб. Перем Базис. перем. |
Х4 |
X5 |
Свободные члены |
Симплексные отношения |
X3 |
-0,6 |
18 |
124,8 |
|
X1 |
0,07 |
1 |
46,5 |
|
X2 |
-1 |
-12 |
6,9 |
|
F-строка |
0,73 |
5 |
552,9 |
Ответ: если предприятие будет выпускать продукцию вида P1 и P2, в количестве 46,5 и 6,9 единиц, то получит максимальную прибыль в размере 552,9 единиц, но так как продукция должна выпускаться только в целых единицах, то тогда предприятие будет выпускать продукцию в количестве 46 и 6 единиц, и получит максимальную прибыль в размере 542 единицы.
Максимальная прибыль для x1=46 и x2=6 находится по формуле:
F max=11*46+6*6=542 единицы.
2.2 Решение задачи линейного программирования графическим способом
Трикотажная фабрика использует для производства свитеров и кофт чистую шерсть, силон и нитрон, запасы, которых составляют 606, 802 и 840 кг. На изготовление свитера расходуется 9 кг шерсти, 15 кг силона и 15 кг нитрона. На изготовление кофты расходуется 27 кг шерсти, 15 кг силона и 3 кг нитрона. От реализации одного свитера фабрика имеет прибыль 11 у. е., а от одной кофты прибыль составляет 6 у. е. Определить максимальную прибыль от реализации всей продукции производства свитеров и кофт.
Таблица 4.
Сорт материала |
Свитер |
Кофта |
Запасы сырья |
Шерсть |
9 |
27 |
606 |
Силон |
15 |
15 |
802 |
Нитрон |
15 |
3 |
840 |
Прибыль (у. е.) |
11 |
6 |
0 |
Решение задачи
Составим математическую модель задачи:
Пусть х1 – единица готовой продукции вида P1,
x2 – единица готовой продукции вида P2,
Цель фабрики получить максимальную прибыль от реализации всей продукции видов P1 и P2, тогда:
F=11x1 + 6x2 → max
Система ограничений:
9x1 + 27x2 ≤ 606
15x1 + 15x2 ≤ 802
15x1 + 3x2 ≤ 840
x1 ≥ 0, x2 ≥ 0 условие неотрицательности.
Используя алгоритм решения и систему ограничений и условия неотрицательности, построим ОДР. Для этого во всех неравенствах системы ограничений и условия неотрицательности знак неравенства заменим на знак равенства. В результате будем иметь уравнения прямых:
F1: 9x1+27x2=606
F2: 15x1+15x2=802
F3: 15x1+3x2=840
x1=0, x2=0
В системе координат построим эти прямые. В результате будем иметь ОДР. В этой же системе координат строим линию уровня и вектор
Рис. 1. Система координат
Так как задача на максимум, будем перемещать линию уровня F=0 вдоль вектора n до тех пор, пока она не пересечет ОДР в самом крайнем своем положении, т.е. при дальнейшем перемещении она не будет с ОДР иметь общие точки. Такой точкой оказалась точка пересечения прямых F1.
Вычислим ее координаты.
9x1+27x2=606
15x1+15x2=802
x1=46,5; x2=6,9; F max=11*46,5+6*6,9=552,9
Таким образом, если предприятие будет выпускать продукцию вида P1 и P2, в количестве 46,5 и 6,9 единиц, то получит максимальную прибыль в размере 552,9 единиц, но так как продукция должна выпускаться только в целых единицах, то тогда предприятие будет выпускать продукцию в количестве 46 и 6 единиц, и получит максимальную прибыль в размере 542 единицы.
Максимальная прибыль для x1=46 и x2=6 находится по формуле:
F max=11*46+6*6=542 единицы.
2.3 Решение задачи линейного программирования с помощью MS EXCEL
Трикотажная фабрика использует для производства свитеров и кофт чистую шерсть, силон и нитрон, запасы, которых составляют 606, 802 и 840 кг. На изготовление свитера расходуется 9 кг шерсти, 15 кг силона и 15 кг нитрона. На изготовление кофты расходуется 27 кг шерсти, 15 кг силона и 3 кг нитрона. От реализации одного свитера фабрика имеет прибыль 11 у. е., а от одной кофты прибыль составляет 6 у. е. Определить максимальную прибыль от реализации всей продукции производства свитеров и кофт.
Таблица 5.
Сорт материала |
Свитер |
Кофта |
Запасы сырья |
Шерсть |
9 |
27 |
606 |
Силон |
15 |
15 |
802 |
Нитрон |
15 |
3 |
840 |
Прибыль (у. е.) |
11 |
6 |
0 |
Решение задачи
Пусть х1 – единица готовой продукции вида P1,
x2 – единица готовой продукции вида P2,
Цель фабрики получить максимальную прибыль от реализации всей продукции видов
P1 и P2, тогда:
F=11x1 +6x2 → max
Система ограничений:
9x1 + 27x2 ≤ 606
15x1 + 15x2 ≤ 802
15x1 + 3x2 ≤ 840
x1 ≥ 0, x2 ≥ 0 условие неотрицательности.
2. Подготовка листа рабочей книги MS Excel для вычислений – на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 2. Переменные задачи находятся, соответственно, в ячейках С3 и С4. Целевая функция находится в ячейке С6 и содержит формулу: =11*С3+6*С4.
Ограничения на задачу учтены в ячейках С8:D10.
Рис. 2. Рабочий лист MS Excel для решения задачи
3. Работа с надстройкой
Поиск решения –
Рис. 3. Установка необходимых параметров задачи в окне Поиск решения
Результат работы по поиску решения помещен на рис 4.
Рис. 4. Результат расчета надстройки Поиск решения
Если предприятие будет выпускать продукцию вида P1 и P2, в количестве 46,5 и 6,9 единиц, то получит максимальную прибыль в размере 552,9 единиц, но так как продукция должна выпускаться только в целых единицах, то тогда предприятие будет выпускать продукцию в количестве 46 и 6 единиц, и получит максимальную прибыль в размере 542 единицы.