Примеры выполнения заданий

Задания:

1 Построить модель производственной задачи, использующей две технологии и три вида ресурсов при значениях величин aij, bi, и bj,. заданных таблицей 30.

 

Таблица 30 — Исходные данные

 

Решить задачу графически.

 

Решение. Математическая модель задачи в численном виде может быть записана следующим образом:

mах Z: 3х1 + 2х2, при ограничениях

х1 + 3х2 <= 270,

4x1 + 6х2 <= 600,

3x1 + х2 <= 240,

x1 >= 0, x2 >= 0.

Для построения допустимой области решений, заданной ограничениями - неравенствами, построим на плоскости многоугольник, ограниченный прямыми х1 + 3х2 = 270, 4x1 + 6х2 = 600, 3x1 + х2 = 240 (линии 1, 2 и 3 на рисунке 1) и координатными

осями x1 = 0, x2 = 0. Убедимся, что любая точка, лежащая внутри или на границе заштрихованной области, удовлетворяет всем исходным неравенствам системы, подставляя любую из точек заштрихованной области, например, начало координат (0; 0) в каждое

из неравенств системы.

 

Рисунок 1 — Решение

 

a) х1 + 3х2 = 270, b) 4x1 + 6х2 = 600 c) 3x1 + х2 = 240

x1=90, x2=60, x1=0, x2=100, x1=0, x2=240,

x1=0, x2=90, x1=150, x2=0, x1=80, x2=0.

 

Приравняем правую часть уравнения целевой функции некоторой постоянной величине Z = 90 и построим уравнение прямой 3x1 + 2х2 = 90 (х1 = 0, х2 = 45; х2 = 0, х1 = 30). Увеличивая Z, будем передвигать эту прямую параллельно самой себе в направлении вектора V = (с12)= (3; 2), координатами которого являются коэффициенты при неизвестных уравнения прямой Z. Он перпендикулярен этой прямой и указывает направление возрастания Z. Максимальное значение Z = 300 достигается в точке С с координатами (60; 60), которая является точкой пересечения прямых 4x1 + 6х2 = 600, и 3x1 + х2 = 240.

 

 

2 Найти оптимальное сочетание посевов пшеницы и кукурузы на участках различного плодородия площадью 100 и 200 га.

Данные приведены в таблице 31.

 

 

Таблица 31 — Исходные данные

 

 

По плану должно быть собрано не менее 1500 ц. пшеницы и 4500 ц. кукурузы. Цена 1 ц. пшеницы 6 денежных единиц, кукурузы - 4 денежных единицы. Критерием оптимальности считается максимум валовой продукции в денежном выражении.

 

Решение Если обозначить через х1 — площадь, отводимую под посев пшеницы на 1 участке, через х2 — на 2, через х3 и х4 площади, отводимые под посев кукурузы соответственно на 1 и 2 участках, то ограничения задачи запишутся следующим образом:

x1 + х3 = 100,

х2 + х4 = 200,

20х1 + 15х2 >= 1500 (ограничение на сбор пшеницы),

35 х3 +30х4 >= 4500 (ограничение на сбор кукурузы),

х j>= 0 (j= 1,4).

Стоимость пшеницы, которую предполагается собрать с двух участков, составляет 6 (20х1 + 15х2) денежных единиц; стоимость кукурузы - 4 (35 х3 +30х4) денежных единиц, а общая стоимость валовой продукции выразится суммой Z= 120х1 + 90х2 + 140х3 + 120х4, которая должна стремиться к максимуму

Для решения задачи графическим способом преобразуем составленную модель в каноническую форму введением дополнительных переменных х5 >= 0 и х6 >= 0:

Max Z = 120х1 + 90х2 + 140х3 + 120х4+ 0х5 + 0х6;

х1 + х3 = 100,

х2 + x4 =200,

20х1 + 15х2 – x5 = 1500

35 х3 +30х4 – x6 = 4500

хj>0 (j= 1,6).

 

 

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

max Z; = 38000 - 20 х1 - 30х2,

x3 = 100- х1, = 200 - х2,

x5 = -1500+20х1 +15 x2,

х6 = 4500-35х1 -30х2.

Перейдем к эквивалентной системе неравенств, опуская базисные переменные х4, х5 и х6:

max Z = -20 х1 - 30 х2 + 38000,

x1< =100,

х2 <= 200,

20х1+ 15х2 >= 1500,

35х1 +30х1 <=4500,

x1>= 0, х2 >= 0.

Решение полученной двумерной задачи приведено на рисунке 2.

 

Рисунок 2 — Решение

 

При этом на каждой граничной прямой одна из переменных исходной задачи обращается в нуль. Так, неравенству 20 х1+ 15х2 >= 1500 соответствует граничная прямая АВ с уравнением 20х1 + 15х2 = 1500.

Но указанное неравенство образовано из третьего уравнения системы ограничений х5 =- - 1500 + 20х1 + 15х2 путем отбрасывания переменной х5, следовательно, на прямой АВ х5 =0.

20х1+15х2= 1500 ; 35х+30x = 4500;

x1 = 0, х2 = 100, х1 = 0, х2 = 150,

х2 = 0, х1 = 75, х2=0, х1 = 128,75.

 

 

Из рисунка 2 видно, что наибольшего значения функция Z достигает в т. А пересечения прямых АВ и АЕ (х2 = 0), имеющей координаты (75; 0), т.е. х1 = 75, х2 = 0. Одновременно в этой вершине х5 = 0.

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

 

х3 = 100—75=25, х4=200, х6 = 2375, при этом Z =36500.

 

Таким образом, пшеницу следует посеять только на первом участке и засеять ею площадь в 75 га; кукурузу надо посеять на обоих участках, причем на первом - 25, а на втором – 200 га. Тогда валовая продукция достигнет (в денежном выражении) максимума и составит 36500 денежных единиц.

Дополнительные переменные х5 и х6 , которые в канонической записи задачи соответственно равны х5 = (20 х1 + 15 х2) - 1500 и х6 = (35 х1 + 30 х2) - 4500, имеют вполне определенный экономический смысл: это превышение сбора пшеницы и кукурузы над плановым заданием. При найденном оптимальном сочетании посевов задание по сбору пшеницы будет выполнено (х5 = 0), а по кукурузе перевыполнено на 2375 ц. (х6 = 2375).

 

Задания:

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

2 Решить графическим методом задачу 2 первого задания.

3 Решить графическим методом задачу 3 первого задания.

4 Решить графическим методом задачу 4 первого задания.

5 Решить графическим методом задачу 5 первого задания.

6 Решить графическим методом задачу 6 первого задания.

7 Решить графическим методом задачу 7 первого задания.

8 Решить графическим методом задачу 9 первого задания.

9 Решить графическим методом задачу 29 первого задания.

10 Решить графическим методом задачу 35 первого задания.

 

Решить графическим методом следующие задачи линейного программирования при целевой функции: mах Z = х1 + 2х2.

 


1 - x1 + x2 < = 2,

1+2х2<=10,

1-2х2<=5,

х1>= 0, х2 >= 0.

 

2 - x1 + 2x2 < = 4,

12 >= 3,

1-3х2 <=12,

х1>= 0, х2 >= 0.

 

3 x1 + 2x2 > = 2,

12<=8,

1-3х2<=12,

х1>= 0, х2 >= 0.

 

 

4 - x1 + 2x2 < = 4,

1-х2<=6,

12<=24,

х1>= 0, х2 >= 0.

 

5 3x1 - x2 > = 3,

-2х1+3х2<=12,

12<=8,

х1+4х2>=8,

х1>= 0, х2 >= 0.

 

6 3x1 - x2 > = 1,

1+3х2<=13,

12<=9

х1+4х2>=9,

х1>= 0, х2 >= 0.


 

 

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

 

7 mах Z =4 х1 + 2х2.

1+3х2<=18,

1+3х2<=9,

1 - х2<=10,

х1>= 0, х2 >= 0.

 

8 mах Z = х1 + 2х2.

1+2х2<=11,

-2х12<=2,

х1 - 3х2<=0,

х1>= 0, х2 >= 0.

 

9 mах Z = 2х1 + 8х2.

х1 - х2<=1,

12<=2,

х1 - х2>=0,

х1>= 0, х2 >= 0.

 

10 mах Z = 2х1 + 3х2.

1+2х2>=6,

х1+4х2>=4,

х1>= 0, х2 >= 0.

 

11 mах Z = 2х1 + 4х2.

1+2х2<=11,

-2х12<=2,

х1 - 3х2<=0,

х1>= 0, х2 >= 0.

 

12 mах Z = х1 - 2х2.

х1 - 2х2 <=1,

х12 >=2,

х1 - 2х2<=0,

х1>= 0, х2 >= 0.

 

13 mах Z = 2х1 + 4х2.

1+3х2<=40,

12х1+3х2<=24,

х1 <= 3, х2 <=3,

х1>= 0, х2 >= 0.

 

14 mах Z = х1 + х2.

х1+2х2<=10,

х1+2х2>=2,

1 + х2<=10,

х1>= 0, х2 >= 0.

 

15 mах Z = 3х1 + 2х2.

х12 >=1,

-5х12<=0,

1 - х2 >=0,

х1 2 >= - 1,

х12 <=6,

х1>= 0, х2 >= 0.