Линейная производственная задача

 x ₄(4y₁ + 2y₂   - 30) = 0  

Ранее было найдено, что в решении исходной задачи х₁>0,  x₂>0.  Поэтому

2y₁ + 3y₂ + 2y₃ - 26= 0

   5y₁  +  y₃ - 35 = 0

Если же учесть, что третий ресурс был избыточным и, согласно той же теореме двойственности, ее двойственная оценка равна нулю т.к. x7=5

У₃=0,

то приходим к системе уравнений

                                                              2y₁ + 3y₂ - 26= 0

   5y₁  -35 = 0

 

откуда следует 

                                                у₁=7,  у₂=4.

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

 

                           у₁=7;  у₂=4;   у₃=0,                           (4)

 

причем общая оценка всех ресурсов равна 1218.

 Заметим,  что решение (4) содержалось в  последней строке последней симплексной  таблицы исходной задачи. Важен  экономический смысл двойственных  оценок. Например, двойственная оценка  третьего ресурса у₂=4 показывает, что добавление одной единицы второго ресурса обеспечит прирост прибыли в 4 единицы.

 

 

 

Задача «о расшивке узких мест производства»

Таблица №3

			26	35	18	30	0	0	0
С	Б	Н	x1	x2	x3	x4	x5	x6	x7
35	x2	14	0	1	-11/15	8/15	1/5	-2/15	0
26	x1	28	1	0	7/3	2/3	0	1/3	0
0	x7	5	0	0	1/15	-28/15	-1/5	-8/15	1
	P	1218	0	0	17	6	7	4	0

 

При выполнении оптимальной производственной программы  первый и третий ресурсы используются полностью, т.е. образуют «узкие места  производства». Будем их заказывать дополнительно. Пусть  – вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие , где Н – значения базисных переменных в последней симплексной таблице, а Q^-1 – обращенный базис, который образуют столбцы при балансовых переменных в этой таблице. Задача состоит в том, чтобы найти вектор , максимизирующий суммарный рост прибыли

                               (1)

при условии  сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой  продукции)

                  (2)

предполагая, что можно надеяться получить дополнительно не более первоначального объема ресурса каждого вида                                      (3)

причем по смыслу задачи       ,                                                                                 (4)

Переписав неравенства (2) и (3) в виде:                            (5)

                     ;         (6)

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. Допустимое множество закрашено серым цветом. Программа «расшивки» имеет вид:

Ответ: максимальный прирост прибыли составит maxW=175.

 

…

 

 

 

 

 

 

 

  Задача о комплектном плане

 

Задачу  ЛП с двумя переменными можно  решить графически. Возьмем на плоскости  систему координат: ось OX₁ направим горизонтально и вправо, ось OX₂ – вертикально и вверх. Каждое ограничение задачи, раз оно линейное нестрогое неравенство, графически изображается полуплоскостью, граничная прямая которой соответствует уже не неравенству, а равенству. Допустимое множество задачи является пересечением всех этих полуплоскостей и есть выпуклый многоугольник.

Вторая  из двух основных теорем ЛП гласит: Если экстремум целевой функции достигается  на допустимом множестве, то функция  принимает его в какой-то вершине  многоугольника – допустимого множества. Исходя из этой теоремы, найти искомый  экстремум можно просто перебрав вершины многоугольника и определив  ту, в которой значение функции  экстремально. Чаще делают по-другому: строят линию уровня целевой функции  и двигают ее параллельно в  направлении экстремума, стараясь уловить  последнюю точку пересечения  линии с допустимым множеством. Зададим  задачу ЛП с тремя ограничениями  и четырьмя переменными, затем зададим  выражения x₃ и x₄ через x₁ и x₂ . Теперь переменных осталось две и задача может быть решена графически.

26	35	18	30
2	5	1	4	126
3	0	7	2	84
2	1	4	0	75

Предположим, что в линейной производственной задаче продукция производится комплектно: продукции 3-го вида надо произвести в 2 раза больше, чем 1-го, а 4-го столько  же, сколько и 2-го вида продукции. Т.е. имеем соотношения x₃=2x₁ и x₄=x₂.

 

62	65
4	9	126
17	2	84
10	1	75

 

 

P=62x₁+65x₂→max

4x₁+9x₂≤126 (1)

17x₁+2x₂≤84   (2)

10x₁+1x₂≤75 (3)

         x₁, x₂³0

 

Искомая точка находится как решение  системы:

Ответ: x₁=3.48; x₂=12.42; maxP=1023.06.

 

 

 

       

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Транспортная  задача формулируется следующим  образом. Однородный продукт, сосредоточенный  в m пунктах производства (хранения) в количествах   а₁, а₂,..., а_m единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно   b₁, b₂,..., b_n единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна с_ij  и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Обозначим через  х_ij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления

       (1)

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

найти план перевозок       

                                        Х = (х_ij),      i = 1,m;        j =  1,n

      

минимизирующий общую стоимость всех перевозок

           (2)

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

      (3)

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

       (4)        

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

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

 

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

А(а₁, а₂, а₃) = (60; 50; 70);    В(b₁, b₂, b₃, b₄) =(56; 35; 48; 30);          2  5  1  4

                                                                                                С = 4  4  3  2           

                                                                                                     6  5  4  3

Общий объем  производства åа_i = 60+50+70= 180 больше, требуется всем потребителям åb_i = 56+35+48+30 = 169, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 180-169 = 11 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

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

 

 

 

 

Имеем:

по\пн	56	35	48	30	Ф 11	Р
60	2         2     56 0	5         5      4 0	4         1      3	3         4      1	0         0      0	P1=0
50	1         4      -3	4         4      31 0	3         3      19 0	2         2      0	-1       0      -1	P2=-1
70	2         6      -4	5         5      0	4         4     29 0	3         3     30 0	0         0     11 0	P3=0
q	q1=2	q2=5	q3=4	q4=3	q5=0

 

Ĉij   Cij      xij Dij

Cij-тарифная стоимость перевозки 1 единицы груза;

Ĉij-фактическая стоимость перевозки 1 единицы груза;

Dij-условие оптимальности;

рi-платежи за единицу груза в пункте отправления;

pj- платежи за единицу груза в пункте назначения

pi + qj = Cij

Для заполненных (базисных)клеток : Ĉij=Cij

Для пустых: Xij=0

Lопорная=56*2+4*5+31*4+19*3+29*4+30*3=519(общая сумма затрат)

Проверка  на оптимальность

Т.к. не все Dij £ 0, то мы еще не нашли оптимальное решение.

Далее выбираем пустую клетку таблицы с максимальной переплатой Dij³0.

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

по\пн	56	35	48	30	Ф 11	Р
60	2         2     56 0	2         5      4 -3	1         1      4 0	0         4      -4	-3         0      -3	P1=0
50	4         4      0	4         4      35 0	3         3      15 0	2         2      0	-1       0      -1	P2=2
70	5         6      -1	5         5      0	4         4     29 0	3         3     30 0	0         0     11 0	P3=3
q	q1=2	q2=2	q3=1	q4=0	q5=-3