Прикладная математика 2 (стр. 3 из 10)
При этом, для сохранения структуры плана производства величины t1, t2, t3должны изменяться лишь в области устойчивости двойственных оценок, т.е. должно выполняться условие:
H + Q-1T
0, причем, по смыслу задачи t1 >0, t2 >0. (1)Таким образом, проблема «расшивки узких мест производства» представляет собой задачу линейного программирования: найти план расшивки - вектор T (t1, t2, 0), максимизирующий суммарный прирост прибыли:
, (2)
при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы).
Обращенный базис был найден при решении задачи симплексным методом:
Условия (1) запишутся в виде:
(3)Предположим также, что поставщики сырья могут выделить компании не более 1/3 первоначального объема ресурса каждого вида:
(4)Перепишем неравенства (3) и (4) в виде:
(5)Задача оптимизации плана «расшивки узких мест» производства принимает вид: найти переменные t1 и t2, которые обеспечивают максимум линейной форме:
, при ограничениях (5).
Решение:
Сформулированная задача линейного программирования с двумя переменными может быть решена графически.
Строим график и ищем точки пересечения: 
, откуда оптимальный план «расшивки»: 
При этом прирост прибыли составит: W = 7t1 + 4t2=447 ½ .
Сводка результатов приведена в таблице:
| Cj | 30 | 25 | 14 | 12 | b | x4+i | yi | ti |
| 2 | 3 | 0 | 4 | 148 | 0 | 7 | 41 5/6 | |
| aij | 4 | 1 | 5 | 0 | 116 | 0 | 4 | 38 2/3 |
| 0 | 2 | 4 | 3 | 90 | 18 | 0 | 0 | |
| xj | 20 | 36 | 0 | 0 | 1500 | 447 ½ | ||
| Δj | 0 | 0 | 6 | 16 |
3. Транспортная задача линейного программирования
Задание:
Составить математическую модель транспортной задачи по исходным данным:
; 
; 
Если полученная модель окажется открытой, то свести ее к замкнутой и найти оптимальное решение транспортной задачи методом потенциалов.
Постановка задачи:
Однородный продукт, сосредоточенный в трехпунктах производства (хранения) в количествах 35, 55 и 80 единиц, необходимо распределить между n-четырьмя пунктами потребления, которым необходимо соответственно 30, 55, 44, 42 единиц. Стоимость перевозки единицы продукта из i-го пункта отправления (
) в j-ый пункт назначения ( 
) равна сij и известна для всех маршрутов. Она задана матрицей С:
Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.
Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика (
) j-му ( ) потребителю. При наличии баланса производства и потребления 
(1)Общий объем производства åаi= 80+50+35= 170 меньше , требуется всем потребителям åbi= 30+55+44+42=171.
Таким образом, имеет место дисбаланс между запасами и запросами. В математическом плане это означает, что наша задача – это задача открытого типа. Для устранения дисбаланса (приведения задачи к закрытому типу), введем фиктивный пункт производства с объемом производства, равным указанному дисбалансу т.е.
единице, причем тарифы на перевозку из этого пункта условимся считать равными нулю ( 
).Четырьмя условиями того, что из каждого пункта хранения вывозится весь продукт, являются:
Четырьмя условиями того, что каждому потребителю доставляется затребованное им количество продукта являются:
| B A | b1=30 | b2=55 | b3=44 | b4=42 | ||||
| a1=35 | x11 | 2 | x12 | 3 | x13 | 6 | x14 | 4 |
| a2=55 | x21 | 4 | x22 | 1 | x23 | 5 | x24 | 7 |
| a3=80 | x31 | 5 | x32 | 2 | x33 | 3 | x34 | 3 |
| a4=1 | x41 | 0 | x42 | 0 | x43 | 0 | x44 | 0 |
В качестве показателя эффективности выступает суммарная стоимость перевозок (L):
;В качестве критерия эффективности правомерно считать принцип минимизации результата т.к. на лицо стремление уменьшить стоимость перевозок. Приходим к следующей математической постановке задачи: найти план перевозок x, компоненты которого обеспечивают минимизацию линейной формы L, при следующих ограничениях на эти компоненты:
(1)Решение:
Сформулированная задача является задачей линейного программирования, которая обладает двумя особенностями, а именно
1) коэффициент при каждой из неизвестных в системе ограничений (1) равен 1;
2) одно из уравнений системы ограничений линейно зависит от других, в силу чего число базисных неизвестных в системе равно
.Эти особенности позволяют решить задачу специально разработанными методами: методом северо-западного угла или методом наименьших затрат. Мы решим ее двумя способами.
Метод наименьших затрат
| потреб произв | b1=30 | b2=55 | b3=44 | b4=42 | |||||
| a1=35 |   30 | 2 | 3 | 6 |  5 | 4 | p1=0 | ||
| a2=55 |  0 | 4 | 55 | 1 |  * | 5 | 7 | p2=2 | |
| a3=80 | 5 | 2 |  44 | 3 | 36 | 3 | p3=-1 | ||
| a4=1 | 0 | 0 | 0 | 1 | 0 | p4=-4 | |||
| q1=2 | q2=-1 | q3=4 | q4=4 | ||||||
