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

Содержание 

     Рассмотрим три  отрасли промышленности I, II, III, каждая из которых производит свой однородный продукт и для обеспечения производства нуждается в продукции других отраслей. Процесс производства рассматривается за определенный период времени (например, за год). Взаимодействие отраслей определяется матрицей прямых затрат. Число , стоящее на пересечении -й строки и -ого столбца, равно , где - поток средств производства из -й отрасли в -ю, а - валовой объем продукции -ой отрасли (все объемы продукции выражаются в единицах стоимости). Задан вектор объемов продуктов конечного потребления.

      , .

1. Определить, является ли матрица продуктивной.
2. Составить уравнение межотраслевого баланса.
3. Найти объем валовой продукции каждой отрасли .
4. Составить матрицу потоков средств производства .
5. Найти объемы валового выпуска продукции, если конечное потребление по отраслям увеличится на 60, 70, 30 соответственно.

     Расчеты рекомендуем проводить с точностью  до двух знаков после запятой.

     Решение.

1. Определить, является ли матрица продуктивной.

      .

     Для решения вопроса о продуктивности матрицы [1] следует найти собственные значения этой матрицы. Составим характеристическое уравнение:

      ,

     или

     

     

     

     На  рисунке изображен график функции 

     

     

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

2. Составить уравнение межотраслевого баланса.

     Модель  межотраслевого баланса, разработанная  профессором В. Леонтьевым (Гарвардский  университет, США), имеет вид:

      ,или, в матричной форме,

     AX + Y = X,

     где А = (a _{i j}) - матрица коэффициентов прямых затрат, Х - вектор валовых выпусков, Y - вектор конечного продукта.

     

3. .Найти  объем валовой продукции каждой  отрасли  .

       Для определения вектора валовой  продукции имеем формулу . Найдем обратную матрицу для матрицы .

     Обозначим B = E-A, тогда 

     

      .  

     Следовательно,

     

4. Составить матрицу потоков средств производства .

Составим  матрицу Х потоков средств  производства, зная что х_ij=а_ij×х_j,(i,j=1,2,3)

     x₁₁ = 0,1×394,83 = 39,48

     x₁₂ = 0,2×405,9 = 81,18

     x₁₃ = 0,4×435,42 = 174,17

     x₂₁ = 0 ×394,83  = 0

     x₂₂ = 0,4×405,9 = 162,36

     x₂₃ = 0,1×435,42 = 43,54

     x₃₁ = 0,1×394,83 = 39,48

     x₃₂ = 0,3×405,9 = 121,77

     x₃₃ = 0,4×435,42 = 174,17

5. Найти объемы валового выпуска продукции, если конечное потребление по отраслям увеличится на 60, 70, 30 соответственно.

, , ,

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

     В таком случае компоненты находятся из матричного уравнения . По заданию 3

     

      .

 

     Организации, занимающейся перевозкой и продажей продукции, необходимо перевезти партию товара. При этом можно арендовать для перевозки по железнодорожной дороге 5- и 7- тонные контейнеры. 5-тонные контейнеры имеется в наличии не более 24 штук, а 7 тонных не более 20 штук. На перевозку всей продукции выделено не более 90 тысяч рублей, причем цена за аренду 5-тонного контейнера – 2тыс. рублей, а 7-тонного – 3 тыс. рублей. Определить сколько и каких контейнеров следует арендовать, чтобы общий объем грузоперевозок был максимальным.

     Решение задачи оформить поэтапно:

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

     Если  x1 и x2 – искомые количества каждого вида контейнеров, то искомый максимальный объем грузоперевозки

     

     при этом:

     Полученная  модель – задача линейного программирования (ЗЛП), записанная в стандартной форме.

     Решим ее графическим методом.

     Строим  прямую 2x₁ + 3x₂ = 90 по двум точкам, например L(0;30), M(45;0) и показываем решение неравенства 2x₁ + 3x₂ £ 90 штриховкой. Решением этого неравенства являются все точки прямой 2x₁ + 3x₂ = 90 и точки полуплоскости лежащей ниже этой прямой.

     Решение неравенства 0 £ x₁ £ 24 и 0 £ x₂ £ 20

     Общее решение удовлетворяющее всем трем неравенствам – выпуклый многоугольник ОАВСD, где О (0;0), А (0;20), В (15;20), С (24;14) и D (24;0). Это и есть многоугольник допустимых решений. Координаты х₁ и х₂ всех точек этого многоугольника удовлетворяют системе ограничений.

     Найдем  такую из них с координатами х_{1 орt} и х_{2 орt}, в которой целевая функция Z достигает максимума Z_max. Для этого построим одну из линий уровня целевой функции, например Z = 0 (ее уравнение 5х₁ +7х₂ = 0) и вектор возрастания целевой функции .

     

     _Рис.1 

      

• Будем перемещать прямую Z = 0 в направлении вектора N. Значение целевой функции при этом будет возрастать и линия уровня будет пробегать через все точки многоугольника допустимых решений. Придельная положение линии уровня, при котором она имеет одну общую точку С с многоугольником ОАВСD соответствует максимальному значению целевой функции.

Z_max = Z (C)=5 ´ 24 +7 ´14 =218.

х_{1 орt} = х₁(С) = 24.  х_{2 орt} = х₂(С) = 14. 

 

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

• Технологические коэффициенты , которые указывают, сколько единиц -го вида сырья требуется для производства одной единицы -го вида продукции;
• Прибыль , получаемая от производства -го вида продукции (в нижней строке таблицы);
• Запасы сырья в планируемый период (в тех же единицах).

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

     Решение задачи оформить поэтапно:

• Составить математическую модель задачи;
• Привести задачу к каноническому виду, пояснить экономический смысл дополнительных переменных;
• Решить задачу симплекс-методом;
• Определить количество неизрасходовапннного сырья при найденном оптимальном плане;
• Построить двойственную задачу, решить её;
• Дать экономический анализ двойственной задачи, оценить целесообразность введения в план нового вида продукции, если затраты на производство этой продукции и получаемая прибыль заданы в последней графе таблицы.

 

Таблица 1.

Решение.

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

     Составим  математическую модель задачи.

     Если  , , , – искомые количества каждого вида продукции, то искомая прибыль

при этом:

     Полученная  модель – задача линейного программирования (ЗЛП), записанная в стандартной форме.

Приведем  задачу к каноническому виду, для  чего введем новые переменные ( в 1 неравенство); ( во 2 неравенство); ( в 3 неравенство); ( в 4 неравенство); с такими знаками перед ними, чтобы неравенства обратились в уравнения, и вместо Z max введем L = - Z min.

Получим:

(1)

 

 

1) Найдем какой-либо опорный план C₀, принимаемый за исходный план перебора. Для этого преобразуем систему уравнений (1) в базисную, в которой четыре переменные (базисные) выражены через оставшиеся четыре (свободные) переменные.

 (2)

Система (2) равносильна системе (1) и имеет  бесчисленное множество решений.

В частности, при  , то . Это решение записывается обычно в виде и называется исходным опорным планом ЗЛП.

 

Если  записать целевую функцию как  функцию свободных переменных то видно, что план X₀ не оптимальный, т.к. целевую функцию можно уменьшить, увеличивая , , , . Причем более эффективное уменьшение целевой функции происходит с ростом x₃.

2) Чтобы  получить более оптимальный план  X₁, в котором x₃ было бы больше нуля, из системы (2) получим новую базисную систему, в которой x_3, была бы переведена из свободных переменных в базисные.

Определим какую из переменных следует перевести вместо x₃ в свободные. Для этого составим и решим систему неравенств из условия, что

Видим, что в новом базисе х₃ можно увеличить до 200. Причем ограничение на рост х₃ связано с переменной х₈. Поэтому в новом базисе х₈ переведем в свободные переменные.

Таким образом:

 (3)

, то  .

 

 

Проанализируем  план X₁ на оптимальность.

План  X₁ не оптимальный, т.к. значение целевой функции можно уменьшить, увеличивая х₂.

3) Получим  новый план X₂, более оптимальный чем X₁. Для этого в новой базисной системе (4) х₂ переведем из свободных переменных в базисные. Для выяснения, какую из переменных (х₃, х₅, х₆; х₇) следует перевести в свободные, составим и решим систему неравенств из условия, что _.

.

Ограничение на рост х₂ в новом базисе связано с переменной х₅; ее и следует перевести в свободные переменные

(4)

при , то .

 

 

Проанализируем  план X₂ на оптимальность.

 

С ростом свободных переменных функция  L не убывает, значит

Возвращаясь к системе (1), обратим внимание на экономический смысл переменных :. – это разности между запасами сырья I, II, III, IV

 и  их расходом на производство  продукции А, B, С, D вида.

Из решения  следует, что при оптимальном  плане производства х_2opt =100/3, х_3opt = 200 запасы сырья I, IV будут исчерпаны полностью, (х₅ = х₈ = 0), а сырье II, III будет израсходовано частично. Остаток сырья II – х₆ =250/3. Остаток сырья III – х₇ =400. 
 

 

Список литературы.

1. Агальцов В.П., Волдайская И.В. «Математические методы в программировании», М.: - ИНФРА-М, 2006. – 224с.
2. Зайченко Ю.П. Исследование операций 2002-2004 [электронный ресурс] – Режим доступа http://iasa.org.ua/iso.php?lang=rus
3. Использование систем линейных уравнений [электронный ресурс] – Режим доступа : http://www.mathelp.spb.ru/book1/sistem_econ.htm
4. Коэффициент вариации [электронный ресурс] – Режим доступа http://www.infamed.com/stat/s02.html
5. Никитенков В.Л. Задачи линейного программирования и методы их решения, СГУ – 2002 [электронный ресурс] – Режим доступа http://www.syktsu.ru/fac/math/app/lp.htm