Математическое программирование и моделирование в экономике и управлении — страница 5

  • Просмотров 3327
  • Скачиваний 257
  • Размер файла 90
    Кб

требуется найти план транспортных связей между поставщиками и потребителями продукции, при котором потребности всех потребителей были бы удовлетворены с минимальными суммарными затратами на поставку всей продукции. xij – объём поставки от i-поставщика к j-потребителю (искомая величина) Поставщики и их мощности Потребители и их спрос B1 ………………………….. Bj ………………………………….. Bn b1 …………………………… bj ………………………………….. bn С=[

сij] mxn / Х=[ xij]mxn A1 a1 c11 ……………………. x11………………… c1j …………………. ………x1j……… c1n ……………… ………….. x1n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ai ai ci1 ……………………. xi1………………… cij …………………. ………xij……… cin ……………… ………….. xin . . . . . . . . . . . . . . . Am am cm1 ……………………. xm1………………… c11 …………………. ………xmj……… c11 ……………… …………..xmn Целевая функция: (1) Условие реализации продукции у каждого из поставщиков: (2) Условие обеспечения всех

потребителей продукцией по их потребности: (3) Условие не отрицательности переменных: В решении системы линейных уравнений 2 и 3 необходимо найти такие не отрицательные значения переменных, чтобы целевая функция принимала минимальное значение. m+n-1 – линейно независимых уравнений, ранг системы, r= m+n-1. В каждом опорном плане должно быть m+n-1 базисных элементов (xij>0), если таких переменных равно или больше, чем m+n-1, план называется

невырожденный; если одна или несколько базисных переменных равна нулю, то такой план считается вырожденным. Открытые транспортные задачи. a) (1) (2) (3) Bn+1: – потребность какого-то потребителя, находящегося за пределами района (фиктивный потребитель). (1) (2) (3) сi, n+1=0 (i=1,2…m) б) (1) (2) (3) Аn+1: – фиктивный поставщик. (1) (2) (3) Ограничение транспортных возможностей. а) xij=0 => cij=М, где М»0; б) 0 ≤ хij ≤ dij dij – характеризует транспортные возможности

между i-поставщиком и j-потребителем. Тогда поставщик Аi условно делится на Аi` и Аi``, при этом ai`=dij и ai``= ai`-dij, cij`=cij и cij``=М, где М»0. Рассмотрим пример решения транспортной задачи методом потенциалов. В1 200 В2 250 В3 275 В4 255 В5 120 Ui A1 300 7 - 10 - M - 6 255 0 45 0 A2 125 9 - 5 125 6 0 8 - 0 - -5 A3 125 9 - 5 125 M - 8 - 0 - -5 A4 270 8 - 6 - 11 195 10 - 0 75 0 A5 280 6 200 11 - 9 80 7 - 0 - -2 Vj -8 10 11 6 0 Δ11=-1 Δ12=0 Δ13=M-11 125 0 0 125 0 125 195 70 Δ21=6 Δ24=7 Δ25=5 Δ31=6 Δ33=M-6 Δ34=7 Δ35=5 Δ41=0 Δ42=-4 Δ44=4 Δ52=13 Δ54=0 Δ55=2

В1 200 В2 250 В3 275 В4 255 В5 120 Ui A1 300 7 - 10 - M - 6 255 0 45 0 A2 125 9 - 5 - 6 125 8 - 0 - -5 A3 125 9 - 5 125 M - 8 - 0 - -1 A4 270 8 - 6 125 11 70 10 - 0 75 0 A5 280 6 200 11 - 9 80 7 - 0 - -2 Vj 8 6 11 6 0 Δ11=-1 Δ12=4 Δ13=M-11 Δ21=6 0 45 200 155 45 0 75 120 70 25 80 125 Δ22=4 Δ24=7 Δ25=5 Δ31=2 Δ33=M-10 Δ34=3 Δ35=1 Δ41=0 Δ44=4 Δ52=7 Δ54=3 Δ55=2 В1 200 В2 250 В3 275 В4 255 В5 120 Ui A1 300 7 45 10 - M - 6 255 0 - 0 A2 125 9 - 5 - 6 125 8 - 0 - -4 A3 125 9 - 5 125 M - 8 - 0 - 0 A4 270 8 - 6 125 11 25 10 - 0 120 1 A5 280 6 155 11 - 9 125 7 - 0 - -1 Vj 7 5 10 6 -1 Δ12=5 0 25 25 0 155 130 125 150 Δ13=M-10 Δ15=1 Δ21=6 Δ22=4 Δ24=6 Δ25=5 Δ31=2