Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Решение задачи 1.3




Максимизировать целевую функцию:

Y=-4x1-x2+3x3-2x4 → max

При ограничениях:

1x1+2x2+0x3+0x4 ≥ 3

-2x1+0x2+0x3+2x4 ≤ -9

-x1-x2+x3+2x4 ≤ -5

x1+0x2-2x3+x4 ≥ 2

x1,2,3,4 ≥ 0

 

Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x5, x6, x7 и x8.

1x1+2x2+0x3+0x4 -1x5+0x6+0x7+0x8=3

2x1+0x2+0x3-2x4 +0x5-1x6+0x7+0x8=9

x1+x2-x3-2x4 +0x5+0x6-1x7+0x8=5

x1+0x2-2x3+x4 +0x5+0x6+0x7-1x8=2

Выразим допустимый базис в форме Таккера:

X5=-3-(-1x1-2x2+0x3+0x4)

X6=-9-(-2x1+0x2+0x3+2x4)

X7=-5-( -x1-x2+x3+2x4)

X8=-2-( -x1+0x2+2x3-x4)

Целевая функция в форме Таккера:

Y=0-(4x1+x2-3x3+2x4)

На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.10).

Таблица 1.10

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
X5 -3 -1 -2
X6 -9 -2
X7 -5 -1 -1
X8 -2 -1 -1
Y -3

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X6. Результат отображен в таблице 1.11.

Таблица 1.11

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
X5 3/2 -2 -1 -1/2
X1 9/2 -1 -1/2
X7 -1/2 -1 -1/2
X8 5/2 -2 -1/2
Y -18 -3

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем двойственный симплекс-метод. Вводим в базис X2, выводим из базиса X7. Результат отображен в таблице 1.12.

Таблица 1.12

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
X5 5/2 -2 -3 1/2 -2
X1 9/2 -1 -1/2
X2 1/2 -1 -1 1/2 -1
X8 5/2 -2 -1/2
Y -37/2 -2 3/2

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X3, выводим из базиса X8. Результат отображен в таблице 1.13.

Таблица 1.13

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
X5 -5 -2
X1 9/2 -1 -1/2
X2 7/4 -2 1/4 -1 1/2
X3 5/4 -1 -1/4 1/2
Y -16

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



 

Ответ : Решение оптимально

Y=-16

X=(9/2;7/4;5/4;0;5;0;0;0)

Количество итераций=3

 

 


Выводы к Главе 1

 

§ В первой главе на примере данных трех задач продемонстрированы основные этапы и приемы, применяемые при решении задач линейного программирования.

§ Сложность решения задач линейного программирования определяется количеством переменных и ограничений в исходной задачe. Количество итераций зависит от того, на сколько «далеко» находится начальное базисное решение от оптимального.


Целочисленное программирование

Решение полностью целочисленной задачи

Максимизировать целевую функцию:

Y=-4x1-x2+3x3-2x4 → max

При ограничениях:

x1+2x2+0x3+0x4 ≥ 3

-2x1+0x2+0x3+2x4 ≤ -9

-x1-x2+x3+2x4 ≤ -5

x1+0x2-2x3+x4 ≥ 2

x1,2,3,4 ≥ 0 и целые


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.009 сек.)Пожаловаться на материал