Автор работы: Пользователь скрыл имя, 22 Апреля 2013 в 18:18, курсовая работа
Целью данной курсовой работы является: освоить навыки использования геометрического метода для решения задач линейного программирования. Для этого были поставлены следующие задачи:
1) Изучить теоретические сведения, необходимые для решения задач линейного программирования геометрическим методом.
2) Разобрать алгоритм решения ЗЛП геометрическим методом.
3) Решить поставленные задачи, используя рассмотренный метод решения задач линейного программирования.
Введение 3
I. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ 4
1.1 Линейное программирование. 4
1.2 Формулировка задачи. 5
1.3 Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования. 7
1.4 Математические основы решения задачи линейного программирования графическим способом. 9
1.4.1 Математический аппарат. 9
1.4.2 Геометрическая интерпретация задачи линейного программирования. 11
1.4.3 Этапы решения графического метода задач линейного программирования 13
II. ПРАКТИЧЕСКИЙ РАЗДЕЛ 18
Задача № 1. 18
Задача № 2. 21
Задача № 3. 24
Задача № 4. 27
Задача № 5. 30
Заключение. 33
Список литературы 34
5х1 + 6х2 ≤ 30
х1 ≥ 0, х2 ≥ 0.
Изобразим многоугольник решений данной задачи.
В ограничениях задачи поменяем знаки неравенства на знаки равенства.
Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).
Рисунок 1.
Рисунок 2.
Заштрихованная область, изображённая на рисунке, является областью допустимых значений функции Z. Т.к. целевая функция Z стремиться к max, то идя по направлению вектора n, получим точку C с оптимальным решением. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:
8х1 + 5х2 ≤ 40 х1 = 3,91,
5х1 + 6х2 ≤ 30, х2 = 1,74. , т. е. C(3,91; 1,74)
максимальное значение линейной функции равно :
Zmax = 50*3,91 + 40*1,74 = 265,10.
Итак, Zmax = 265,10 при оптимальном решении х1 = 3,91, х2 = 1,74, т. е. максимальная прибыль в 1232,80 ден. ед. может быть достигнута при производстве 3,91единиц продукции P1 и 1,74 единиц продукции P2.
Ответ: Zmax = 265,10.
Питательные вещества |
Число единиц питательных веществ в 1 кг корма |
Необходимый минимум питательных веществ | |
A |
B | ||
S1 |
3 |
1 |
8 |
S2 |
1 |
2 |
9 |
S3 |
1 |
6 |
12 |
Минимальная стоимость за 1 кг корма, в руб.. |
4 |
6 |
? |
Имеется два вида корма. A и B, содержащие вещества(витамины) S1, S2, S3. Содержание числа единиц питательных веществ в одном кг каждого вида корма и необходимый минимум самих питательных веществ даны в таблице:
Решение:
Пусть х1 и х2 – количество кормов вида А и В соответственно. В одном килограмме каждого вида корма содержится (3х1 + х2) единиц питательного вещества S1, (x1 + 2x2) - S2 и (x1 + 6x2) - S3. Так количество питательных веществ не должно быть меньше необходимого минимума, то запишем следующую систему неравенств:
3х1 + х2 ≥ 8,
x1 + 2x2 ≥ 9,
x1 + 6x2 ≥ 12,
x1, x2 ≥ 0.
Минимальную стоимость витаминов за 1 кг корма, выразим следующей функцией : F = 4x1 + 6x2 => min.
Изобразим многоугольник решений данной задачи.
В ограничениях задачи поменяем знаки неравенства на знаки равенства.
Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).
Рисунок 1.
Рисунок 2.
Выделенная область, изображённая на рисунке, является областью допустимых значений функции F. Точка В - оптимальное решение. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:
x1 + 2x2 = 9, x1 = 7,50,
x1 + 6x2 = 12, x2 = 0,75.
Минимальное значение линейной функции равно :
Fmin = 4*7.5 + 6*0.75 = 34.50.
Итак, Fmin = 34.50 при оптимальном решении х1 = 7.50, х2 = 0.75.
Ответ: Fmin = 34,50.
Трикотажная фабрика использует для производства свитеров и кофточек шерсть, силикон и нитрон, запасы которых составляют 820, 430 и 310 кг. Количество пряжи каждого вида (в кг), необходимой для изготовления одного изделия, а также прибыль, получаемая от их реализации, приведены в таблице.
Вид сырья. |
Нормы расхода пряжи. |
Запас | |
Свитера. |
Кофточки. | ||
Шерсть |
0,4 |
0,2 |
820 |
Силон |
0,2 |
0,1 |
430 |
Нитрон |
0,1 |
0,1 |
310 |
Прибыль |
7,8 |
5,6 |
? |
Определить план выпуска изделий, максимизирующий прибыль.
Решение.
Пусть х1 и х2 – норма расхода пряжи для свитеров и кофточек соответственно. Количество пряжи каждого вида (в кг), необходимой для изготовления одного изделия запишем в следующую систему неравенств:
0,4х1 + 0,2х2 ≤ 820,
0,2x1 + 0,1x2 ≤ 430,
0,1x1 + 0,1x2 ≤ 310,
x1, x2 ≥ 0.
Максимальная прибыль от реализации свитеров и кофточек выразим следующей функцией : F = 7,8x1 + 5,6x2 => max.
Изобразим многоугольник решений данной задачи.
В ограничениях задачи поменяем знаки неравенства на знаки равенства.
Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).
Рисунок 1.
Рисунок 2.
Выделенная область, изображённая на рисунке, является областью допустимых значений функции F. Точка В - оптимальное решение. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:
0,4x1 + 0,2x2 = 820, x1 = 1000,
0,1x1 + 0,1x2 = 310, x2 = 2100.
Максимальное значение линейной функции равно :
Fmax = 7.8*1000 + 5.6*2100 = 19560.
Итак, Fmax = 19560 при оптимальном решении х1 = 1000, х2 = 2100.
Ответ: Fmax = 19560.
На звероферме могут выращиваться чёрно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используются три вида кормов. Определить, сколько лисиц и песцов следует выращивать на звероферме, чтобы прибыль от реализации их шкурок была максимальной.
Вид корма. |
Кол-во единиц корма, которое должны получать. |
Общее кол-во корма | |
Лисица |
Песец. | ||
I |
2 |
3 |
180 |
II |
4 |
1 |
240 |
III |
6 |
7 |
426 |
Прибыль |
16 |
12 |
? |
Решение:
Пусть х1 и х2 – количество единиц корма, которые должны получать лисиа и песец, соответственно. Количество единиц каждого вида корма, необходимого для выращивания одного животного запишем в следующую систему неравенств:
2х1 + 3х2 ≤ 180,
4x1 + 1x2 ≤ 240,
6x1 + 7x2 ≤ 426,
x1, x2 ≥ 0.
Максимальная прибыль от реализации шкурок выразим следующей функцией : F = 16x1 + 12x2 => max.
Изобразим многоугольник решений данной задачи.
В ограничениях задачи поменяем знаки неравенства на знаки равенства.
Построим в программе Excel таблицы нахождения точек пересечения линий с осями координат (Рисунок 1) и график (Рисунок 2).
Рисунок 1.
Рисунок 2.
Выделенная область, изображённая на рисунке, является областью допустимых значений функции F. Точка С - оптимальное решение. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:
x2 = 0, x1 = 60,
4x1 + x2 = 240, x2 = 0.
Максимальное значение линейной функции равно :
Fmax = 16*60 + 12*0 = 960.
Итак, Fmax = 960 при оптимальном решении х1 = 60, х2 = 0.
Ответ: Fmax = 960.
Заключение
В данной курсовой работе
мною были освоены навыки решения
задач линейного
В первых двух случаях задача может иметь единственное решение в конкретной точке, а также в любой точке отрезка или луча.
Таким образом, освоив все необходимые навыки использования геометрического метода для решения задач линейного программирования, я решила поставленные задачи.
Список литературы
Информация о работе Решения задач линейного программирования геометрическим методом