Шпаргалка: 5 различных задач по программированию
из условия (3) следует t2£148/3, t3£158/3 (6)
приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).
Эту задачу легко решить графически: см. рис. 2. Программа ²расшивки² имеет вид
t1 =0, t2 =14, t3 =0 и прирост прибыли составит 112.
Сводка результатов приведена в таблицe 2.
| сj | 36 | 32 | 10 | 13 | b | x4+i | yi | ti |
| 2 | 3 | 4 | 1 | 103 | 5 | 0 | 0 | |
| aij | 4 | 2 | 0 | 2 | 148 | 0 | 8 | 14 |
| 2 | 8 | 7 | 0 | 158 | 0 | 2 | 0 | |
| xj | 31 | 12 | 0 | 0 | 1500 | 112 | ||
| Dj | 0 | 0 | 4 | 3 |
ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Однородный продукт, сосредоточенный в 3 пунктах производства (хранения) в количествах 40; 60; 70 единиц, необходимо распределить между 4 пунктами потребления, которым необходимо соответственно 36; 32; 40; 53 единиц. Стоимость перевозки единицы продукта из пункта отправления в пункт назначения известна для всех маршрутов и равна С = 
. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.
Для решения транспортной задачи чаще всего применяется метод потенциалов .
Общий объем производства åаi =40+60+70=170 больше, чем требуется всем потребителям åbi = 36+32 +40 +53 =161, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 170-161 = 9 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.
Первое базисное допустимое решение легко построить по правилу ²северо-западного угла².
 Потребление | b1 =36 | b2 =32 | b3 =40 | b4 =53 | b5 =9 |
 Производство | |||||
| а1 =40 | 36 | 4 | p1 =0 | ||
| a2 =60 | 28 | 32 | p2 = | ||
| a3 =70 | * | 8 | 53 | 9 | p3 = |
| q1 = | q2 = | q3 = | q4 = | q5 = |
Общая стоимость всех перевозок для первого базисного допустимого решения:
L = 36* 2 + 4 *3 + 28 *2 + 32 + 8* 7+ 53 =281
Один из потенциалов можно выбрать произвольно, так как в системе (3), (4) одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток 
. В данном случае получаем
D11 = 0, p1 + q1 - c11 = 0, 0+q1 -2 = 0, q1 = 2
D12 = 0, p1 + q2 - c12 = 0, 0+q2 -3 = 0, q2 = 3
D22 = 0, p2 + q2 - c22 = 0, р2 +3-2 = 0, р2 = -1
и т.д., получим: q3 =2, p3 =5, q4 = -4, q5 = -5.
Затем по формуле (6) вычисляем оценки всех свободных клеток:
D21 = p2 + q5 - c21 = -1+2-4 = -3
D31 = p3 + q1 - c31 = 5+2-2 = 5
D32 = 1; D13 = -2; D14 = -5; D24 = 0; D15 = -5; D25 = -6.
Находим наибольшую положительную оценку max (
) = 5 = 
Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 31-11-12-22-23-33. Производим перераспределение поставок вдоль цикла пересчета
| 36 | 4 | 36-r | 4+r | 28 | 12 | |
  | 28 | 32 | 28-r | 32+r | 20 | 40 |
| 8 | r | 8-r | 8 |
= 8
Получаем второе базисное допустимое решение:
 bj | b1 =36 | b2 =32 | b3 =40 | b4 =53 | b5 =9 |
| ai | |||||
 а1 =40 | 28 | 12 | * | p1 =0 | |
| a2 =60 | 20 | 40 | p2 = -1 | ||
| a3 =70 | 8 | 53 | 9 | p3 =0 | |
| q1 =2 | q2 = 3 | q3 = 2 | q4 = 1 | q5 =0 |
Находим новые потенциалы, новые оценки.
D13 = -2; D14 = 0; D15 = 0; D21 = -3; D24 = -2; D25 = -1; D32 = -4; D33 = -5,
т.е. все Dij £ 0 i = 1,m; j = 1,n
Общая стоимость всех перевозок для второго базисного допустимого решения: