Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Постановка задачи линейного программирования
в стандартной форме (СЗЛП).
Найти вектор x= (x1...,xn), что минимизирует целевую функцию
L(x)= c1x1 +... + cnxn (2.1)
и удовлетворяет систему ограничений
a11x1 +... + a1n xn = a10
....................... (2.2)
am1x1 +... + amnxn = am0
xj ³ 0, j=1...,n. (2.3)
В задаче (2.1)–(2.3) будем называть матрицу A=||aij||, i=1...,m, j=1...,n, матрицей условий; вектор-столбец Aj= (a1j..., amj) т, j=1...,n — j-м вектором условий; вектор A0= (a10..., am0) т— вектором ограничений.
Основные определения.
Вектор x= (x1...,xn) называется допустимым решением ЗЛП, если его компоненты удовлетворяют ограничение (2.2)–(2.3).
Ненулевое допустимое решение x — базисный (ДБР), если его положительным компонентам xj отвечают линейно независимые векторы условий Aj. (Нулевое допустимое решение будем всегда считать базисным).
Система m линейно независимых векторов условий, что включает указанные векторы Aj, называется базисом.
Векторы базиса образуют базисную матрицу.
Изложение симплекс-метода.
Симплекс-метод (СМ) непосредственно применяется к развязыванию каноничной задачи линейного программирования (КЗЛП) и осуществляет целеустремленное перебирание допустимых базисных решений (ДБР ) ( вершин допустимого многогранника решений ЗЛП, что определяется ограничениями (2.2)–(2.3)), к множеству которых принадлежит оптимальное решение, если он существует; или определяет, что ЗЛП не имеет оптимального решения.
ЗЛП — каноничная, если ее ограничения (2.2) имеют каноничную форму:
xi + ai,m+1 xm+1 +... + ainxn = ai0, ai0 ³ 0, i=1...,m
то есть, матрица условий A=||aij||, i=1...,m, j=1...,n, заключает в себе единичную подматрицу размера m ´ m и вектор ограничений A0= (a10..., am0) т— неотъемлемый.
КЗЛП элементарно определяет такие основные в линейном программировании конструкции:
· некоторый ДБР — x(0)=( a10..., am0,0,...,0);
· его базис — m-мерные единичные векторы (1,0...,0) т, (0,1...,0) т..., (0...,0,1) т;
· его базисную матрицу B — единичную матрицу размера m ´ m;
· базисные переменные — x1..., xm.
Стандартная ЗЛП (2.1)–(2.3) сводится в общем случае к каноничной ЗЛП добавлением искусственных неотъемлемых переменных к левым частям ограничений (2.2) и введением этих же переменных с достаточно большим коэффициентом М>0 к целевой функции (2.1) (М-метод).
М-задача имеет вид:
L(x)= c1x1 +... + cnxn + M (y1 +... + ym) ® min
a11x1 +... + a1n xn + y1 = a10
............................,
am1x1 +... + amnxn + ym = am0
xj ³ 0, j=1...,n, yi ³ 0, i=1...,m
ai0 ³ 0, i=1...,m.
Признак оптимума: Если на некотором шаге СМ симплекс - разницы (см. алгоритм) ДБР x* незначительные, то x* — оптимальное решение КЗЛП.
Условия отсутствия решения:
1. ЗЛП не имеет оптимального решения, если на каком-либо шаге хотя бы один вектор условий Aj с отрицательной оценкой D j не имеет положительных компонент;
2. ЗЛП не имеет решений, если хотя бы одна искусственная переменная положительная в случае, когда выполняется признак оптимума.
Алгоритм симплекс-метода.
На каждом шагу СМ выполняются такие действия (расчетные формулы наводятся лишь для первого шага).
1. Рассматривается ДБР x= (a10..., am0,0,...,0).
Вычисляются относительные оценки (симплекс - разницы) D j небазисных переменных xj, j=m+1...,n, за формулой:
D j=cj – (cб, Aj)
где cб= (c1..., cm), Aj — вектор условий, что отвечает переменной xj (относительные оценки базисных переменных приравняются нулю).
Если для всех j=1...,n, выполняется условие D j ³ 0, то ДБР x является оптимальным решением КЗЛП. Если к тому же все искусственные переменные равняются нулю, то, отбрасывая их, получим оптимальное решение исходной ЗЛП; иначе исходная ЗЛП не имеет решений (ее допустимая область пустая).
Если существует такое j, что D j<0, а вектор условий Aj не имеет положительных компонент, то ЗЛП не имеет оптимального решения (ее целевая функция L (x) не ограничена снизу на допустимом многограннике решений). Конец вычислений.
2. Если существуют индексы j, для которых D j<0, а соответствующие векторы условий Aj имеют положительные компоненты, то находят k за формулой
k=argmin D j
j: D j<0
и, вычисляя для aik>0 отношения qi=ai0/aik, определяют l, что удовлетворяет соотношение
l=argminqи.
и: aik>0
3. Переходят к новому ДБР, путем введения к базису вектора Ak и выведения из базиса вектора Al. Такой переход осуществляется с помощью симплекс - превращений (элементарных превращений Жордана - Гаусса) с ведущим элементом alk над элементами расширенной матрицы условий (2.2). Переход к пункту 1.
Программное обеспечение.
Обучающий модуль, с помощью которого ЗЛП решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО. Геометрическая интерпретация задачи линейного программирования осуществляется модулем, который вызывается из того же самого раздела.
Задание.
Решить симплекс-методом задачи линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1-№9), а также следующие задачи.
Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые.
1) | x1 + x2 + x3 ® min | 2) | 2 x1 + x2 – x3 – x4 ® min |
x1 – x4 – 2 x6 = 5 | x1 + x2 + 2 x3 – x4 = 2 | ||
x2 + 2 x4 – 3 x5 + x6 = 3 | 2 x1 + x2 – 3 x3 + x4 = 6 | ||
x3 + 2 x4 – 5 x5 + 6 x6 = 5; | x1 + x2 + x3 + x4 = 7; |
3) | x1 – 2x2 + 3x3 ® min | 4) | 2x1 – 3x2 ® max | 5)) | 6 x1 + 4 x2 ® min |
2x1 + 3x2 + 4x3 = 1 | 5x1 + 2x2 ³ 10 | 2 x1 + x2 ³ 3 | |||
–2x1 + x2 + 3x3 = 2; | x1 + 3x2 £ 12; | x1 – x2 £ 1; |
6) | 2 x1 – 4 x2 ® min | 7) | 7 x1 + 5 x2 ® max | 8) | 3 x1 + 2 x2 ® max |
8 x1 – 5 x2 £ 16 | 7 x1 + 5 x2 ³ 7 | 4 x1 + 2 x2 ³ 12 | |||
x1 + 3 x2 ³ 2 | 7 x1 – 5 x2 ³ 35 | x1 + 2 x2 £ 10 | |||
2 x1 + 7 x2 £ 9; | x1 – x2 £ 0; | 2 x1 + 2 x2 = 6; |
9) | 4 x1 + 5 x2 + 9 x3 + 11 x4 ® max | 10) | 2 x1 + x2 – x3 – x4 ® min |
x1 + x2 + x3 + x4 £ 15 | x1 + x2 + 2 x3 – x4 = 2 | ||
7 x1 + 5 x2 + 3 x3 + 2 x4 £ 80 | 2 x1 + x2 – 3 x3 + x4 = 6 | ||
3 x1 + 5 x2 + 10 x3 + 15 x4 £ 60; | x1 + x2 + x3 + x4 = 7; |
11) | 4x1 + x2 – 2x3 – x4 – x5 ® min | 12) | x1 + 2 x2 + 3 x3 – x4 ® max |
x3 – x4 + x5 = 1 | x1 + 2 x2 + 3 x3 = 15 | ||
x2 + 2x4 – x5 = 1 | 2 x1 + x2 – 3 x3 = 20 | ||
x1 + 2x2 + 2x5 = 4; | x1 + 2 x2 + x4 = 10. |
Ответы:
1) x* = (7.1; 0; 0; 1.3; 0; 0.4), L (x*)= 7.1.
2) x* = (0; 4.13; 0.25; 2.63), L (x*)= 1.25.
3) Решения нет (D = Æ).
4) x* = (12; 0), L (x*)= 24.
5) x* = (1.33; 0.33), L (x*)= 9.33.
6) x* = (0; 1.29), L (x*)= -5.14.
7) Решения нет (целевая функция неограниченна сверху на допустимом множестве).
8) x* = (3; 0), L (x*)= 9.
9) x* = (10.16; 0; 2.95; 0), L (x*)= 67.21.
10) x* = (0; 4.13; 0.25; 2.63), L (x*)= 1.25.
11) x* = (0; 0; 0.5; 1.5; 2), L (x*)= -4.5.
12) Решения нет (D = Æ).
Лабораторная работа 3.
Дата публикования: 2014-11-04; Прочитано: 943 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!