3. Транспортная  задача линейного программирования

  Имеется 3 производителя однородной продукции, имеющие запасы этой продукции 50, 70 и 30 единицы соответственно. Также  имеется 4 потребителя данной продукции. Их потребность составляет 30, 11, 45 и 36 единицы соответственно. Транспортная компания заключила контракт с поставщиками и потребителями на вывоз и поставку данной продукции от производителей к потребителям. При перевозке продукции от каждого производителя к каждому потребителю транспортная компания имеет определённые издержки на единицу продукции: 3 у.е. при перевозке от 1-ого производителя к 1-ому потребителю, 2 у.е. - от 1–ого производителя ко 2-ому потребителю, 6 у.е. – от 1-ого к 3-ему, 7 у.е. – от 1-ого к 4-ому, 7 у.е. – от 2-ого к 1-ому, 8 у.е. – от 2-ого ко 2-ому, 3 у.е. – от 2-ого к 3-ему, 5 у.е. – от 2-ого к 4-ому, 3 у.е. – от 3-его к 1-ому, 3 у.е. – от 3-его ко 2-ому, 4 у.е. – от 3-его к 3-ему, 6 у.е. – от 3-его к 4-ому. Так как естественным стремлением транспортной компании является максимизация прибыли, то требуется составить такой план перевозок, чтобы издержки были минимальными.

   Можно записать эти издержки на единицу  продукции  в виде матрицы, где  строка издержки при поставке от одного производителя к каждому потребителю, а столбец издержки при поставке к одному потребителю от каждого производителя:

Предложение производителей и спрос  потребителей можно записать в виде векторов А и B соответственно:    
 

  Требуется найти план перевозок Х = (х_ij), i = 1,m; j =  1,n  минимизирующий общую стоимость всех перевозок

                                                                    (2)

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

      (3)

и любому потребителю  доставляется необходимое количество груза

       (4)

причем по смыслу задачи

х₁₁ > 0 ,. . . .,  x_mn > 0.                                              (5)

В нашей  задаче 4 потребителя и 3 поставщика, причём суммарный объем производства Sa_i = 50 + 70 + 30 = 150 больше, чем требуется всем потребителям Sb_i = 30 + 11 + 45 + 36 = 122, т.е. имеем открытую модель транспортной задачи Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 150-122 = 28 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю. Фактически эта потребность будет указывать на количество продукции, которая не будет вывозиться от производителя.

  Обозначим количество перевезённой продукции за x. Таким образом, количество перевезённой продукции от 1-ого производителя к 1-ому потребителю будет , а от 1-ого производителя ко 2-ому потребителю - и т.д. Мы получим матрицу одного размера с С:

  

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

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

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

  Первое  базисное допустимое решение легко  построить по правилу ²северо-западного угла².

Пусть p и q – двойственные переменные, соответствующие строкам и столбцам таблицы. Если значения x, p и q - допустимые решения соответствующих двойственных задач, то при равенстве целевых функций эти решения – оптимальны. Для того чтобы целевые функции были равны требуется выполнение условий: для базисных переменных и для свободных переменных ( ). Пусть , тогда (для занятых клеток)

∆₁₁= p₁+q₁-C₁₁=0 => q₁ =3

∆₁₂= p₁+q₂-C₁₂=0 => q₂ =2

∆₂₂= p₂+q₂-C₂₂=0 => p₂ =3-6=-3  и т. д.

Произведем  оценку (для свободных клеток), где  нет поставок: 

∆₁₄= p₁+q₄-C₁₄= 0+8-7= 1

∆₁₅= p₁+q₅-C₁₅= 0+2-0= 2

∆₂₁= p₂+q₁-C₂₁= -3+3-7= -7

∆₂₂= p₂+q₂-C₂₂= -3+2-8= -9

∆₂₅= p₂+q₅-C₂₅= -3+2-0= -1

∆₃₁= p₃+q₁-C₃₁= -2+3-4= -3

∆₃₂= p₃+q₂-C₃₂= -2+2-3= -3

∆₃₃= p₃+q₃-C₃₃= -2+6-4= 0 

Так как  решение не оптимально поменяем набор  базисных переменных. Для этого выберем  ячейку, которой соответствует максимальная симплекс-разница ∆₁₅. Для того, чтобы не нарушить равновесия воспользуемся методом циклического пересчёта: 1.5 – 3.5 – 3.4 – 2.4 – 2.3 – 1.3 ρ _max =9

Таким образом, сумма в строках и  столбцах осталась неизменной, а мы получили новое базисное решение:

 
 
 

Находим новые потенциалы, новые оценки. Пусть , тогда (для занятых клеток) 

∆₁₁= p₁+q₁-C₁₁=0 => q₁ =3

∆₁₂= p₁+q₂-C₁₂=0 => q₂ =2 

∆₁₅= p₁+q₅-C₁₅=0 => q₅ = 0и т. д. p₃ = 0, q₄ = 6, p₂ = -1, q₃ = 4

Произведем  оценку (для свободных клеток), где  нет поставок: 

∆₁₃= p₁+q₃-C₁₃= 0+4-6= -2

∆₁₄= p₁+q₄-C₁₄= 0+6-7= -1

∆₂₁= p₂+q₁-C₂₁= -1+3-7= -5

∆₂₂= p₂+q₂-C₂₂= -1+2-8= -7

∆₂₅= p₂+q₅-C₂₅= -1+0-0= -1

∆₃₁= p₃+q₁-C₃₁= 0+3-4= -1

∆₃₂= p₃+q₂-C₃₂= 0+2-3= -1

∆₃₃= p₃+q₃-C₃₃= 0+4-4= 0 

Данное  базисное решение оптимально, так  как все симплекс разницы   

     Ответ:

 

4. Динамическое программирование. Распределение  капитальных вложений

  Динамическое  программирование - это вычислительный метод для решения задач управления определённой структуры. Данная задача с n переменными представляется как много шаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.

  Рассмотрим  нелинейную задачу распределения ресурсов между предприятиями отрасли. Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через f_j(x_j) прирост мощности  или прибыли на  j-том предприятии, если оно получит x_j рублей капвложений. Требуется найти такое распределение (х₁, х₂, ..., х_n) капвложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

  Z=f₁(x₁)+f₂(x₂)+...+f_n(x_n)

  при ограничении по общей сумме капвложений  х₁ + х₂ +...+х_n = b, причём будем считать, что все переменные x_j принимают только целые значения x_j =1,2,...

  Функции f_j(x_j) мы считаем заданными, заметив, что их определение - довольно трудоёмкая экономическая задача.

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

  Введём  параметр состояния и определим  функцию состояния. За параметр состояния x  примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния F_k(x) определим как максимальную прибыль на первых  k  предприятиях, если они вместе получат x рублей. Параметр x может меняться от 0 до b. Если из x рублей k-ое предприятие  получит Х_к  рублей, то каково бы ни было это значение, остальные x-Х_к  рублей естественно распределить между предприятиями от 1-го до (к-1)-го предприятия, чтобы была получена максимальная прибыль F_k-1(x-x_k). Тогда прибыль k предприятий будет равна f_k(x_k) + F_k-1(x-x_k). Надо выбрать такое значение x_k между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению: