Решения задач линейного программирования геометрическим методом
Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.
Решение.
Обозначим через х1 количество единиц продукции Р1, а через х2 – количество единиц продукции Р2. Тогда, учитывая количество единиц сырья, расходуемое на изготовление продукции, а так же запасы сырья, получим систему ограничений:
2х1 + 5х2 ≤ 20
8х1 + 5х2 ≤ 40
5х1 + 6х2 ≤ 30
которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превысит имеющихся запасов. Если продукция Р1 не выпускается, то х1=0; в противном случае x1 = 0. То же самое получаем и для продукции Р2. Таким образом, на неизвестные х1 и х2 должно быть наложено ограничение неотрицательности: х1 ≥ 0, х2 ≥ 0.
Конечную цель решаемой задачи – получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных х1 и х2. Реализация х1 единиц продукции Р1 и х2 единиц продукции Р2 дает соответственно 50х1 и 40х2 руб. прибыли, суммарная прибыль Z = 50х1 + 40х2 (руб.)
Условиями не оговорена неделимость единица продукции, поэтому х1 и х2 (план выпуска продукции) могут быть и дробными числами.
Требуется найти такие х1 и х2, при которых функция Z достинает максимум, т.е. найти максимальное значение линейной функции Z = 50х1 + 40х2 при ограничениях
2х1 + 5х2 ≤ 20
8х1 + 5х2 ≤ 40
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.
Задача № 3
Питательные вещества | Число единиц питательных веществ в 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.
Задача № 4
Трикотажная фабрика использует для производства свитеров и кофточек шерсть, силикон и нитрон, запасы которых составляют 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.
Задача № 5
На звероферме могут выращиваться чёрно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используются три вида кормов. Определить, сколько лисиц и песцов следует выращивать на звероферме, чтобы прибыль от реализации их шкурок была максимальной.
Вид корма. | Кол-во единиц корма, которое должны получать. | Общее кол-во корма | |
Лисица | Песец. | ||
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.
Заключение
В данной курсовой работе мною были освоены навыки решения задач линейного программирования геометрическим методом. Для этого я изучила теоретические сведения, необходимые для решения задач линейного программирования указанным методом. Я узнала, что данный метод применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно. Также я узнала, как строятся прямые на плоскости, для