2015-10-22
324
Метод искусственного базиса
В системе переменная Хn+I образуют искусственный базис. Получение максимального опорного плана исходной задачи основано на следующих утверждениях:
-если в оптимальном плане М задачах все искусственные переменные равны нулю, то план является оптимальным
-если в ОП по крайней мере одна из искусственных переменных положительна, то исходная задача не имеет ни одного плана
-если М задачи не имеет решения, то исходная задача не разрешима
В симплексных таблицах для функции F отводится две строки. Одну для f, другую для М. Если преобразования выполняются с двумя строками, то признак оптимальности сначала проверяется сначала по 2й строке. По ней же проверяются переменные, включаемые в базис. Процесс преобразования продолжается до тех пор, пока из базиса не исключены все искусственные переменные. По мере исключения из базиса этих переменных соответствующие им столбцы можно опускать.
f= -2*x1-6*x2+5*x3-x4-4*x5 (max)
-----
X1-4*x2+2*x3-5*x4+9*x5=3
X2-3*x3+4*x4-5*x5=6
X2-x3+x4-x5=1
-----
|
|
|
X1- так как не входит в след два
-----
X1-4*x2+2*x3-5*x4+9*x5=3
X2-3*x3+4*x4-5*x5+х6=6
X2-x3+x4-x5+х7=1
-----
Задача на максимум, значит в целевую ф они входят с -М
f= -2*x1-6*x2+5*x3-x4-4*x5-М(х6+х7)
x1=3+4*x2-2*x3+5*x4-9*x5
x6=6-x2+3*x3-4*x4+5*x5
x7=1-x2+x3-x4+x5
f= -2*(3+4*x2-2*x3+5*x4-9*x5)-6*x2+5*x3-x4-4*x5-М((6-x2+3*x3-4*x4+5*x5)+(1-x2+x3-x4+x5
))= -6-8*x2+4*x3-10*x4+18*x5-6*x2+5*x3-x4-4*x5-M(7-2* x2+4*x3-5*x4+6*x5)=
=-6-14*x2+9*x3-11*x4+14*x5-M(7-2* x2+4*x3-5*x4+6*x5)
| БП | С5 | А0 | Х2 | Х3 | Х4 | X5 | БП | С5 | А0 | Х2 | Х3 | X5 |
| X1 | -2 | -4 | -5 | X1 | -2 | -3 | ||||||
| X6 | -4 | -3 | -5 | X6 | -4 | -1 | ||||||
| X7 | -1 | -1 | X7 | -1 | -1 | |||||||
| F | -6 | -9 | -14 | F | -11 | -3 | ||||||
| M | -7 | -5 | M | -2 | -1 | |||||||
| БП | С5 | А0 | Х2 | Х5 | БП | С5 | А0 | Х2 | Х3 | X5 | ||
| X1 | -8 | X5 | ||||||||||
| X3 | -2 | -1 | X3 | |||||||||
| X4 | -2 | -1 | X4 | |||||||||
| F | -21 | -1 | F | -7 |
Теорема двойственности
Первая теорема двойственности
Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение. Причём экстремальные значения целевых функций совпадают Z(X*)=f(y*)
| X1 | Ym+1 |
| X2 | Ym+2 |
| X3 | Ym+J |
| X4 | Ym+n |
| Xn+1 | Y1 |
| Xn+2 | Y2 |
| Xn+i | Yi |
| Xn+m | Ym |
Min
Y*i=-X*n+i
Экономический смысл допустим, если задача определения оптимального плана максимизирующего выпуск продукции разрешимо, то разрешимо и задача определения оценок ресурсов (себестоимость равна цене)
| Спрос | П1 | П2 | П3 | П4 | Об. Рес-ов |
| I | 0.5 | ||||
| II | |||||
| III | |||||
| Цена |
75X1+30X2+60X3+120X4àmax
2X1+X2+0.5X3+4X4<=2400|X5
X1+5X2+3X3<=1200|X1
3X1+5X3+X4<=3000|X2
| БП | С5 | А0 | Х1 | Х2 | Х3 | Х4 | X5 | Х6 | X7 |
| X5 | |||||||||
| 0.5 | |||||||||
| X6 | |||||||||
| X7 | |||||||||
| F | -75 | -30 | -60 | -120 | |||||
| БП | С5 | А0 | Х1 | Х2 | Х3 | Х4 | X5 | Х6 | X7 |
| X4 | 1/2 | 1/4 | 1/8 | 1/4 | |||||
| 2.5 | -1/4 | 4.85 | -1/4 | ||||||
| БП | С5 | А0 | Х1 | Х2 | Х3 | Х4 | X5 | Х6 | X7 |
| X4 | 6000/13 | ||||||||
| X3 | 4800/13 | ||||||||
| X1 | 1200/13 | ||||||||
X*=(1200/13;0;4800/13;600013)
|
|
|
Y*=(30;15;0)
В М пунктах отправления А1..Ам сосредоточено определённое количество груза соответственно а1..ам имеющийся груз необходимо доставить потребителям- В1..Вн, спрос которых выражается величиной в1..вн. известна стоимость Сij- перевозки единицы груза из I пункта отправления в j пункт назначения требуется составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе и при этом суммарные транспортные издержки минимизируются.
| Поставщики | В1 | Потребители В2 | … | Вн | Запасы груза Ai |
| А1 | С11 Х11 | С12 Х12 | … | С1н Х1н | а1 |
| А2 | С21 Х21 | С22 Х22 | … | С2н Х2н | а2 |
| Ам | См1 Хм1 | См2 Хм2 | … | Смн Хмн | ам |
| Потребность вj | в1 | в2 | … | вн |
Сумма (Хij)=аi
Сумма(Хij)=вj
--------------------------1
Хij>=0 (i=1,m;j=1,n)
--------------------------2
F= сумма(сумма(Cij*xij))
--------------------------3
Дана система ограничений 1 при условии 2 или линейная функция 3. Требуется среди множества решений системы надо найти такое неотрицательное решение, при котором линейная функция 3 принимает минимальное значение. План перевозок называется допустимым, если он удовлетворяет условиям 1 и 2. Допустимый план перевозок, доставляющий минимум целевой функции называется оптимальным.
Теорема 1:
Для того чтобы транспортная задача имела допустимые планы необходимо и достаточно выполнения равенства- сумма(ai)= сумма(вj), если сумма(ai)>/< сумма(вj), то модель называется открытой. Для разрешимости её необходимо преобразовать в закрытую. Для этого вводим либо фиктивного поставщика, либо фиктивного потребителя. Тариф при этом равен нулю и все тарифы одинаковы- целевая функция не меняется.
Теорема 2:
О ранге матрицы.
Ранг матрицы в транспортной задачи на единицу меньше числа уравнений- Z=m+n-1 (Z-число занятых клеток). Если у нас сумма(ai)>сумма(вj),то необходимо ввести n+1 пункт назначения., т.е. в матрице задачи предусматривается дополнительный столбец и спрос фиктивного потребителя полагается равным Bn+1=сумма(aj)-сумма(вj). Если наоборот, то вводится фиктивный поставщик (am+1=сумма(вj)-сумма(ai))
Построение исходного опорного плана:
1) Правило северо-западного угла:
| Поставщик | В1 | В2 | В3 | ai |
| А1 | -- | -- | ||
| А2 | -- | |||
| А3 | -- | |||
| А4 | -- | -- | ||
| вj |
