Прикладная математика (стр. 5 из 14)
4y1 + 2y3 ³ 25
5y1 + 2y2 + 5y3 ³ 50
причем оценки ресурсов не могут быть отрицательными
y1
0, y2 0, y3 0. (3)Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений
(х1, х2, х3, х4) и 
(y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий  |  |
x 1 (4y1 + 2y2 + 3y3 - 36) = 0 y1 (4x1 +3x2 + 4x3 + 5x4 - 208) = 0
x 2 (3y1 + 5y2 + y3 - 14) = 0 y2 (2x1 +5x2 + 2x4 - 107) = 0
x 3 (4y1 + 2y3 - 25) = 0 y3 (3x1 + x2 + 2x3 + 5x4 - 181) = 0 .
x 4(5y1 + 2y2 + 5y3 - 50) = 0
Ранее было найдено, что в решении исходной задачи х1>0, x4>0. Поэтому
 |
4y1 + 2y2 + 3y3 - 36 = 0
5y1 + 2y2 + 5y3 - 50 = 0
Если же учесть, что второй ресурс был избыточным и, согласно той же теореме двойственности, ее двойственная оценка равна нулю
у2=0,
то приходим к системе уравнений
4y1 + 3y3 - 36 = 05y1 + 5y3 - 50 = 0
откуда следует
у1=6, у3=4.
Таким образом, получили двойственные оценки ресурсов
у1=6; у2=0; у3=4, (4)
причем общая оценка всех ресурсов равна 1972.
(3)
Переписав неравенства (2) и (3) в виде:  |
, t2=0, t3= 
.| сj | 36 | 14 | 25 | 50 | b | x4+i | yi | ti |
| 4 | 3 | 4 | 5 | 208 | 0 | 6 | 46 5/12 | |
| aij | 2 | 5 | 0 | 2 | 107 | 13 | 0 | 0 |
| 3 | 1 | 2 | 5 | 181 | 0 | 4 | 60 1/3 | |
| xj | 27 | 0 | 0 | 20 | 1972 | 519 2/3 | ||
| Dj | 0 | 8 | 7 | 0 |
§7. Транспортная задача линейного программирования
Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в mпунктах производства (хранения) в количествах а1, а2,..., аm единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно b1, b2,..., bnединиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна сijи известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.
Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления
(1)математическая модель транспортной задачи будет выглядеть так:
найти план перевозок
Х = (хij), i = 1,m; j =1,nминимизирующий общую стоимость всех перевозок
(2)при условии, что из любого пункта производства вывозится весь продукт
(3)и любому потребителю доставляется необходимое количество груза
(4)причем по смыслу задачи
х11> 0 ,. . . ., xmn > 0. (5)
 Потребление | b1 =41 | b2 =50 | b3 =44 | b4 =30 | b5 =12 |
 Производство | |||||
| а1 =54 | 41 | 13 | p1 =0 | ||
| a2 =60 | 37 | 23 | p2 = | ||
| a3 =63 | * | 21 | 30 | 12 | p3 = |
| q1 = | q2 = | q3 = | q4 = | q5 = |
Следует иметь в виду, что по любой транспортной таблице можно восстановить соответствующий предпочитаемый эквивалент системы уравнений (3), (4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе (3), (4) ровно m + n - 1 линейно независимых уравнений, то в любой транспортной таблице должно быть m + n - 1 занятых клеток.