Контрольная работа по "Экономико-математической модели"

 

 

Задача 1

Предприятию необходимо перевезти со склада по железной дороге продукцию трех видов: продукции первого вида не более c1 изделий, продукции второго вида не более c2 изделий и продукции третьего вида не более c3 изделий. Для этой перевозки подразделение железной дороги может выделить специально оборудованные вагоны двух типов A и B. Для полной загрузки вагона в него следует помещать продукцию всех трех видов. При этом в вагон типа A входят a1 изделий первого вида, a2 изделий второго вида и a3 изделий третьего вида. В вагон типа B входят b1 изделий первого вида, b2 изделий второго вида и b3 изделий третьего вида. Экономия от перевозки в вагоне типа A составляет a руб., в вагоне типа B – b руб.

 

Вариант	a1	a2	a3	b1	b2	b3	c1	c2	c3	a	b
13	8	7	16	12	9	13	612	493	1036	11	9

 

Требуется:

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

2. Определить сколько вагонов каждого типа следует выделить для перевозки, чтобы суммарная экономия от перевозки была наибольшей? Решить задачу линейного программирования графическим методом.

3. Сформулировать двойственную задачу и найти ее оптимальное решение, используя теоремы двойственности.

 

Решение

Построим математическую модель:

Пусть х1 – количество вагонов 1го типа, х2 – количество вагонов 2го типа.

Тогда количество продукции первого вида составит

Тогда количество продукции второго вида составит

Тогда количество продукции третьего вида составит

Экономия от перевозки будет составлять

Математическая модель имеет вид:

 

 

 

Решим задачу графически:

Необходимо найти максимальное значение целевой функции

F = 11x1+9x2 → max, при системе ограничений:

8x1+12x2≤612	(1)
7x1+9x2≤493	(2)
16x1+13x2≤1036	(3)

 

Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Построим уравнение 8x1+12x2 = 612 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 51. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 76.5. Соединяем точку (0;51) с (76.5;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 8 • 0 + 12 • 0 - 612 ≤ 0, т.е. 8x1+12x2 - 612≤ 0 в полуплоскости ниже прямой.

Построим уравнение 7x1+9x2 = 493 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 54.78. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 70.43. Соединяем точку (0;54.78) с (70.43;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 7 • 0 + 9 • 0 - 493 ≤ 0, т.е. 7x1+9x2 - 493≤ 0 в полуплоскости ниже прямой.

Построим уравнение 16x1+13x2 = 1036 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 79.69. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 64.75. Соединяем точку (0;79.69) с (64.75;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 16 • 0 + 13 • 0 - 1036 ≤ 0, т.е. 16x1+13x2 - 1036≤ 0 в полуплоскости ниже прямой.

или

 

Шаг №2. Границы области допустимых решений.

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

Обозначим границы области многоугольника решений.

 

 

Шаг №3. Рассмотрим целевую функцию задачи F = 11x1+9x2 → max. 

Построим прямую, отвечающую значению функции F = 0: F = 11x1+9x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (11; 9). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

 

 

Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

7x1+9x2=493

16x1+13x2=1036

Решив систему уравнений, получим: x1 = 55, x2 = 12

Откуда найдем максимальное значение целевой функции:

F(X) = 11*55 + 9*12 = 713

Поскольку функция цели F(x) параллельна прямой (3), то на отрезке BA функция F(x) будет принимает одно и тоже максимальное значение.

Для определения координат точки A решим систему двух линейных уравнений:

8x1+12x2=612

7x1+9x2=493

Решив систему уравнений, получим: x1 = 34, x2 = 28.3333

Откуда найдем максимальное значение целевой функции:

F(X) = 11*34 + 9*28.3333 = 713

 

 

Составим двойственную задачу к прямой задаче.

8y1+7y2+16y3≥11

12y1+9y2+13y3≥9

612y1+493y2+1036y3 → min

Отметим, что решение двойственной задачи дает оптимальную систему оценок ресурсов.

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

Подставим оптимальный план прямой задачи в систему ограниченной математической модели:

8*34 + 12*28.33 = 612 = 612

1-ое ограничение прямой  задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью  используется в оптимальном плане, является дефицитным и его  оценка согласно второй теореме  двойственности отлична от нуля (y1>0).

7*34 + 9*28.33 = 493 = 493

2-ое ограничение прямой  задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью  используется в оптимальном плане, является дефицитным и его  оценка согласно второй теореме  двойственности отлична от нуля (y2>0).

16*34 + 13*28.33 = 912.33 < 1036

3-ое ограничение выполняется  как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является  дефицитным и его оценка в  оптимальном плане y3 = 0

С учетом найденных оценок, новая система примет вид:

8y1+7y2≥11

12y1+9y2≥9

612y1+493y2 → min

Решая систему графическим способом, находим оптимальный план двойственной задачи:

 

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (4), то ее координаты удовлетворяют уравнениям этих прямых:

8x1+7x2=11

x1=0

Решив систему уравнений, получим: x1 = 0, x2 = 1.5714

Откуда найдем минимальное значение целевой функции:

F(X) = 612*0 + 493*1.5714 = 774.7143

y1 = 0

y2 = 1.57

Z(Y) = 612*0+493*1.57 = 774.71

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

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:

1-ое ограничение двойственной  задачи выполняется как равенство. Это означает, что продукт №1 экономически  выгодно производить, а его использование  предусмотрено оптимальным планом  прямой задачи (x1>0)

8*0 + 7*1.57 + 0*0 = 11 = 11

12*0 + 9*1.57 + 0*0 = 14.14 > 9

2-ое ограничение выполняется  как строгое неравенство, т.е. продукт  №2использовать экономически не  выгодно. И действительно в оптимальном  плане прямой задачи x2 = 0

 

Задача 2

 

Имеются три пункта поставки однородного груза А1, А2, А3 и пять пунктов В1, В2, В3, В4, В5 потребления этого груза. На пунктах А1, А2 и А3 находится груз в количестве соответственно а1, а2 и а3 т. В пункты В1, В2, В3, В4 и В5 требуется доставить соответственно b1, b2, b3, b4 и b5 т груза. Расстояния между пунктами поставки и пунктами потребления приведены в следующей таблице.

Пункты поставки	Пункты потребления
	В1	В2	В3	В4	В5
А1	d11	d12	d13	d14	d15
А2	d21	d22	d23	d24	d25
А3	d31	d32	d33	d34	d35

 

Требуется:

Составить такой план закрепления потребителей за поставщиками, чтобы общие затраты по перевозкам были минимальными.

Вариант 13

а1 = 200,          b2 = 100,

а2 = 250,          b3 = 120,

а3 = 200,          b4 = 110,

b1 = 190,          b5 = 130,

Решение