Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Южный филиал Национального университета

Читайте также:
  1. Б) На 01.06.2013 совокупный объем средств Фонда национального благосостояния равен 86,72 млрд. долларов США или 2 739,33 млрд. рублей.
  2. Баланс национального богатства
  3. Барнаульский филиал
  4. Бирский филиал ФГБОУ БашГУ
  5. Бирский филиал ФГБОУ БашГУ
  6. Бондырева Светлана Константиновна – ректор Московского психолого-социального университета, доктор псх. наук, профессор, академик РАО - председатель оргкомитета конференции
  7. Владикавказский филиал Финуниверситета
  8. Влияние войны на экономическую и политическую ситуацию в стране. Нарастание общенационального кризиса
  9. Влияние национального права на процесс становления и развития международного права. Воздействие международного права на внутригосударственное право в современных условиях.
  10. Волгоградский филиал

(метод больших штрафов)

 

В этом методе ограничения изменяются введением искусственных переменных таким образом, чтобы экстремальная точка новой задачи находилась достаточно легко. Каждой искусственной переменной назначается большой положительный штраф М с тем, чтобы в оптимальном решении полученной задачи значение этой переменной было равно нулю.

Решим прямую задачу линейного программирования симплексным М-методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции

 

F(X) = 2x1+x2+3x3 при следующих условиях-ограничений (см. также M-задача).
x1+2x2+x3≤1000
3x1+5x2+2x3≤1500
x1≥100
x2≥100
x3≥200


Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

 

1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 = 1000
3x1 + 5x2 + 2x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 = 1500
1x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 = 100
0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 = 100
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 = 200

 

Введем искусственные переменные x.
1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1000
3x1 + 5x2 + 2x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1500
1x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 + 1x9 + 0x10 + 0x11 = 100
0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 + 0x9 + 1x10 + 0x11 = 100
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 + 0x9 + 0x10 + 1x11 = 200

 

Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 2x1+x2+3x3 - Mx9 - Mx10 - Mx11 => max

 

За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:

 

x9 = 100-x1+x6
x10 = 100-x2+x7
x11 = 200-x3+x8
которые подставим в целевую функцию:
F(X) = 2x1 + x2 + 3x3 - M(100-x1+x6) - M(100-x2+x7) - M(200-x3+x8) => max
или
F(X) = (2+1M)x1+(1+1M)x2+(3+1M)x3+(-1M)x6+(-1M)x7+(-1M)x8+(-400M) => max

 

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x9, x10, x11,

 

Переходим к основному алгоритму симплекс-метода.

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
0 x4 1000 1 2 1 1 0 0 0 0 0 0 0 1000
  x5 1500 3 5 2 0 1 0 0 0 0 0 0 750
  x9 100 1 0 0 0 0 -1 0 0 1 0 0 0
  x10 100 0 1 0 0 0 0 -1 0 0 1 0 0
  x11 200 0 0 1 0 0 0 0 -1 0 0 1 200
Индексная строка F(X1) -400M -2-1M -1-1M -3-1M 0 0 1M 1M 1M 0 0 0 0

Иногда такую таблицу представляют с дополнительной строкой для М.

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
x4
  x5
  x9 -1
  x10 -1
  x11 -1
Индексная строка F(X0) -2 -1 -3
M   -400 -1 -1 -1

 

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
1 x4 800 1 2 0 1 0 0 0 1 0 0 -1 800
  x5 1100 3 5 0 0 1 0 0 2 0 0 -2 366.67
  x9 100 1 0 0 0 0 -1 0 0 1 0 0 100
  x10 100 0 1 0 0 0 0 -1 0 0 1 0 0
  x3 200 0 0 1 0 0 0 0 -1 0 0 1 0
Индексная строка F(X2) 600-200M -2-1M -1-1M 0 0 0 1M 1M -3 0 0 3+1M 0

 

Загрузка...
План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
x4 -1 -1
  x5 -3 -2
  x1 -1
  x10 -1
  x3 -1
Индексная строка F(X3) 800-100M -1-1M -2 1M -3 2+1M 3+1M

 

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 min
3 x4 500 0 0 0 1 0 1 2 1 -1 -2 -1 500
  x5 300 0 0 0 0 1 3 5 2 -3 -5 -2 150
  x1 100 1 0 0 0 0 -1 0 0 1 0 0 0
  x2 100 0 1 0 0 0 0 -1 0 0 1 0 0
  x3 200 0 0 1 0 0 0 0 -1 0 0 1 0
Индексная строка F(X4) 900 0 0 0 0 0 -2 -1 -3 2+1M 1+1M 3+1M 0

 

План Базис В x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
4 x4 350 0 0 0 1 -0.5 -0.5 -0.5 0 0.5 0.5 0
  x8 150 0 0 0 0 0.5 1.5 2.5 1 -1.5 -2.5 -1
  x1 100 1 0 0 0 0 -1 0 0 1 0 0
  x2 100 0 1 0 0 0 0 -1 0 0 1 0
  x3 350 0 0 1 0 0.5 1.5 2.5 0 -1.5 -2.5 0
Индексная строка F(X5) 1350 0 0 0 0 1.5 2.5 6.5 0 -2.5+1M -6.5+1M 1M

 

Оптимальный план можно записать так:
x4 = 350
x8 = 150
x1 = 100
x2 = 100
x3 = 350
F(X) = 2*100 + 1*100 + 3*350 = 1350

Южный филиал Национального университета


Дата добавления: 2014-12-15; просмотров: 17 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2017 год. (0.011 сек.)