Контрольная работа по «Высшей математике»

1. Решить графически следующие  задачи линейного программирования

1)                         2)

 

Решение

Каждое неравенство определяет полуплоскость с граничной прямой аi1х1+аi2х2=bi. Условия неотрицательности определяют полуплоскости с граничными прямыми х1=0, х2=0. Полуплоскости пересекаясь, образуют многоугольник решений.

Геометрически задача линейного программирования представляет собой поиск такой точки многогранника решений, координаты которой доставляют линейной функции наибольшее (наименьшее) значение.

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

Этап 2. Прямая, перпендикулярная вектору-градиенту, передвигается в направлении этого вектора до тех пор, пока не покинет пределов многоугольной области.

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

Определим множество решений первого неравенства. Решением уравнения служат точки прямой . Построим прямую по двум точкам (3;0) и (0;1). На рисунке обозначим ее цифрой 1. Областью решения строгого неравенства является верхняя полуплоскость.

Решением второго уравнения служат точки (-3;0) и (0;2). На рисунке она обозначена цифрой 2. Областью решения строгого неравенства является нижняя полуплоскость.

Решением третьего уравнения служат точки (5;0) и точки левее данной прямой. На рисунке она обозначена цифрой 3. Областью решения строгого неравенства является левая полуплоскость.

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

 

 

Рисунок 1.1 - Графический метод решения задачи линейного программирования

 

Первая точка – результат пересечения первого уравнения и оси ОУ, точка А(0;1).

Точка В – результат пересечения второго уравнения и оси ОУ, т.е. В(0;2).

Точка С – результат пересечения второго и третьего уравнения. Решая систему уравнений

,

Получим С (5;16/3).

Точка D – результат пересечения третьего уравнения и оси ОХ, т.е.       D (5;0).

Точка Е – результат пересечения первого уравнения и оси ОХ, т.е.         Е (3;0).

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

 

Приравняем целевую функцию постоянной величине z, . Меняя z, получим семейство линий уровня. Если z=0, вычислим координаты точек, удовлетворяющих уравнению - это точки с координатами (-1;1) и (1;-1). Обозначим линию уровня пунктиром.

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

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

z=2*5+2*16/3=62/3.

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

z=2*0+2*1=2.

 

 

2. Предприятие выпускает два  вида продукции  и . Для их изготовления необходимо затратить такие производственные факторы, как сырье (С), физический труд (Ф) и управленческий труд (У). Затраты ресурсов на изготовление одного изделия вида следующие: С – 8 кг, Ф – 3 чел.-ч., У – 1 чел.-ч. Затраты ресурсов на изготовление изделия вида такие: С – 1 кг, Ф – 1 чел.-ч., У – 2 чел.-ч. Ежедневный объем ресурсов: С – 320 кг, Ф – 150 чел.-ч., У – 200 чел.-ч. Прибыль от реализации одного изделия каждого вида: для - 80 ден.ед., для - 160 ден.ед.

1) построить экономико-математическую  модель задачи

2) графическим методом найти  план выпуска продукции по  видам с учетом ресурсов, который обеспечивал бы предприятию максимальный доход.

 

Решение

Пусть ед. – план выпуска продукции -го вида (j=1,2), – суммарная прибыль. Составим экономико-математическую модель задачи:

- целевая функция – суммарная  прибыль от реализации продукции:

- ограничения:

 

Первое ограничение – это ограничение по ресурсу С, которое составлено исходя из норм его расхода на выпуск продукции и и суммарного его запаса.

Второе ограничение – это ограничение по ресурсу Ф.

Третье ограничение – это ограничение по ресурсу У.

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

Определим множество решений первого неравенства. Решением уравнения служат точки прямой . Построим прямую по двум точкам (40;0) и (0;320). На рисунке обозначим ее цифрой 1. Областью решения неравенства является верхняя полуплоскость.

Решением второго уравнения служат точки (50;0) и (0;150). На рисунке она обозначена цифрой 2. Областью решения неравенства является нижняя полуплоскость.

Решением третьего уравнения служат точки (200;0) и (0;100). На рисунке она обозначена цифрой 3. Областью решения неравенства является левая полуплоскость.

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

 

Рисунок 2.1 - Графический метод решения задачи линейного программирования

 

Первая точка – результат пересечения третьего уравнения и оси ОУ, точка А(0;100).

Точка В – результат пересечения второго и третьего уравнений. Решая систему уравнений

,

Получим В (20;90).

Точка С – результат пересечения второго и первого уравнений. Решая систему уравнений

,

Получим С (34;48).

Точка D – результат пересечения первого уравнения и оси ОХ, т.е.       D (40;0).

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

 

Приравняем целевую функцию постоянной величине z, . Меняя z, получим семейство линий уровня. Если z=0, вычислим координаты точек, удовлетворяющих уравнению - это точки с координатами  (-20;10) и (20;-10). Обозначим линию уровня пунктиром.

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

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

z=8*20+160*90=14560.

 

 

3. На предприятии имеется возможность выпускать три вида продукции . При ее изготовлении используются ресурсы P1,P2 и P3.  Размеры допустимых затрат ресурсов ограничены соответственно величинами b1,b2 и b3.  Расход ресурса i-го (i = 1, 2, 3) вида на единицу продукции j-го вида составляет aij ден. ед. Цена единицы продукции j-го вида равна cj ден. ед.

 

 

Ресурсы	Запас ресурсов, ед.	Нормы расхода сырья на единицу продукции
		П1	П2	П3
Р1	50	3	2	4
Р2	30	2	1	6
Р3	44	3	1	5
Цена единицы продукции, ден.ед.		40	68	53

 

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

 

Решение

Пусть ед. – план выпуска продукции -го вида, – суммарная прибыль. Составим экономико-математическую модель задачи:

- целевая функция:

- ограничения:

 

Чтобы привести ЗЛП к канонической форме, ведем балансовые переменные х4, х5, х6, получаем каноническую форму задачи с базисными переменными х4, х5, х6.

 

 

Построим начальную симплексную таблицу.

 

БП	(B)	СП
		х1	х2	х3
х4	50	3	2	4
х5	30	2	1	6
х6	44	3	1	5
F	0	-40	-68	-53

 

Т.к. в B-столбце нет отрицательных элементов, то план х=(0,0,0,50,30,44) f=0 является опорным, приступим к нахождению оптимального плана.

 

План х=(0,0,0,50,30,44) не является оптимальным, т.к. в F-строке есть отрицательные элементы, минимальный из которых определяет разрешающий столбец переменной х2. Находим симплексные отношения (50/2, 30/1, 44/1), разрешающей будет строка переменной х4.

 

Выполняем перестановку переменных х2 и х4 и пересчитываем симплексную таблицу.

 

БП	(B)	СП
		х1	х4	х3
х2	25	3/2	1/2	2
х5	5	½	-1/2	4
х6	19	3/2	-1/2	3
F	1700	62	34	83

 

Полученный план х=(0,25,0,0,5,19) f=1700 является опорным и оптимальным, т.к. в F-строке нет отрицательных элементов.

Оптимальный план имеет вид х=(х*1=0, х*2=25, х*3=0, х*4=0, х*5=5, х*6=19).

Следовательно, предприятию выгодно производить только продукцию второго вида в количестве 25 ед. При этом полученная прибыль будет равна 1700 ден.ед. Ресурсы использованы следующим образом: I – полностью, П – не полностью (остаток составляет 5 ед., Ш – не полностью (остаток составляет 19 ед.).

 

4. Используя условие задачи 3:

1) сформулировать в экономических  терминах двойственную задачу  и составить ее математическую  модель

2) используя решение задачи 3 и соответствие между переменными, найти компоненты оптимального плана двойственной задачи – двойственные оценки .

 

Решение

Переменные называются двойственными (или объективно обусловленными) оценками. В данной задаче введем переменные по числу ограничений в прямой задаче.

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

Запишем двойственную задачу и воспользуемся решением прямой задачи для определения оптимального плана.

 

- целевая функция:

- ограничения:

 

Составим таблицу соответствия переменных прямой и двойственной задач.

 

Оптимальный план выпуска продукции			Остатки запасов на складе
Х1	Х2	Х3	Х4	Х5	Х6
0	25	0	0	5	19
62	0	83	34	0	0
Y4	Y5	Y6	Y1	Y2	Y3
Превышение затрат над ценой реализации			Теневые оценки ресурсов  (оптимальный план двойственной задачи)

 

Оптимальный план двойственной задачи (y1*= 34, y2*= 0, y3*= 0) единиц. Максимальная прибыль равна 1700 ед.