Решение и постоптимальный анализ задачи линейного программирования

• Уменьшатся (в случае знака ограничения "<")

• Увеличивается (в случае знака ограничения ">").

Пусть S0 - значение соответствующей дополнительной переменной в точке оптимума. Тогда решение остаётся допустимым и оптимальным в диапазоне bi+ ∆ , где

Дефицитные ресурсы

Если в оптимальном решении некоторая дополнительная переменная небазисная, то суще

ствующее ' ей ограничение является связывающим (активным в точке оптимума), а ресурс - дефицитным.

Для ограничения типа "<":

Для ограничения типа ">":

Изменение коэффициентов Ц.Ф.

Существует диапазон изменения коэффициентов ' целевой функции как базисных так и не базисных переменных, в которых полученное решение остаётся оптимальным. Изменение коэффициента базисной переменной в пределах этого диапазона приводит к изменению значения целевой функции, так как Z = Ств*β, а одна из компонент вектора Св изменяется. Изменение коэффициента небазисной переменной не меняет значения задачи.

Для задачи на mах:

Базисные переменные:

Для базисной переменной диапазон устойчивости, в котором может изменяться коэффициент Ci , оставляя текущее решение оптимальным, задаётся выражением: Ci + ∆

где dj - относительная оценка переменной xj в текущем оптимальном решении.

Eсли отсутствуют соответственно.

Не базисные переменные:

Для не базисной переменной диапазон устойчивости, в котором может изменятся коэффициент Сi оставляя текущее решение оптимальным, задаётся выражением:

Для задачи на min: Базисные переменные:

Для базисной переменной диапазон устойчивости, в котором может изменяться коэффициент Сi , оставляя текущее решение оптимальным, задаётся выражением: Сi + ∆

He базисные переменные:

Для не базисной переменной диапазон устойчивости, в котором может изменятся коэффициент С; оставляя текущее решение оптимальным, задаётся выражением:

(dN) < ∆ < ∞

2. Содержательная постановка задачи

Вариант 3/2

Транспортная компания для перевозки инжира из Багдада в Мекку использует мулов, одногорбых и двугорбых верблюдов. Двугорбый верблюд может перевезти - 1000 фунтов, одногорбый – 500 фунтов, а мул – 300 фунтов. За один переход двугорбый верблюд потребляет 2 кипы сена и 40 галлонов воды. Одногорбый верблюд потребляет 2 кипы сена и 30 галлонов воды. Мул – 1 кипу сена и 10 галлонов воды. Пункты снабжения компании, расположенные в различных оазисах вдоль пути, могут выдать не более 900 галлонов воды и 35 кип сена. Верблюды и мулы арендуются у пастуха близ Багдада, арендная плата равна 12 пиастрам за двугорбого верблюда, 5 пиастрам за одногорбого и 4 пиастрам за мула.

Если компания должна перевести 8000 фунтов инжира из Багдада в Мекку, сколько надо использовать верблюдов и мулов для минимизации арендной платы пастуху?

3. Математическая постановка задачи

Переменные:

Х1 - Двугорбый верблюд

Х2 - Одногорбый верблюд

Х3 – Мул

Целевая функция – минимизация арендной платы.

Zmin = 12Х1 + 5Х2+ 4Х3

Ограничения:

Использования ресурса «вода» не более 900 галлонов:

40Х1 + 30Х2+ 10Х3 < 900

Использования ресурса «сено» не более 35 кип:

3Х1 + 2Х2+ Х3 < 35

Компания должна перевести 8000 фунтов инжира:

1000Х1 + 500Х2 + 300Х3 =8000

Все переменные должны быть не отрицательны:

Х1, Х2, Х3 > 0

4. Решения задачи симплекс-методом

ЦФ:

Zmin = 12X1 + 5X2 + 4X3

Ограничения:

40X1 + 30X2 + 10X3 < 900

3X1 + 2X2 + X3 < 35

1000X1 + 500X2 + 300X3 = 8000

X1, X2, X3 > 0

Приведем задачу к канонической форме и введём искусственные переменные:

Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 – MR1

40X1 + 30X2 + 10X3 + 0S1 = 900

3X1 + 2X2 + X3 + 0S2 = 35

1000X1 + 500X2 + 300X3 + R1 = 8000

X1, X2, X3 > 0

R1 = – 1000X1 – 500X2 – 300X3 + 8000

Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 – M (– 1000X1 – 500X2 – 300X3 + 8000) = (12 + 1000M) X1 + (5 + 500M) X2 + (4 + 300M) X3 – 8000M

Z + (–12 – 1000M) X1 + (–5 – 500M) X2 + (–4 – 300M) X3 = – 8000M

Составляем симплекс таблицу:

 Скачать реферат