Лекция 3
.pdfТЕОРЕМА О ДОПУСТИМЫХ БАЗИСНЫХ РЕШЕНИЯХ
Каждомудопустимомубазисномурешению задачилинейного программированиясоответствуетугловаяточкамногогранникарешений, инаоборот,каждойугловойточке многогранникарешенийсоответствует допустимоебазисноерешение.
ПРАВИЛАВЫБОРА РАЗРЕШАЮЩЕГО СТОЛБЦА И РАЗРЕШАЮЩЕЙ СТРОКИ
Разрешающий столбец определяет НАИБОЛЬШИЙ (ПО МОДУЛЮ)
ОТРИЦАТЕЛЬНЫЙ коэффициент Сj в нижней строке.
Разрешающая строка определяется по минимальному соотношению, вычисляемого по следующим правилам:
1.∞, если bi и aij имеют разные знаки.
2.∞, если bi = 0 и aij < 0.
3.∞, если aij = 0.
4.0, если bi = 0 и aij > 0.
5.| bi / aij |, если bi и aij имеют одинаковые знаки.
На пересечении разрешающей строки и разрешающего столбца
находится разрешающий элемент aij.
11
18/3
16/1
5/1
∞
Переходк следующей таблицейосуществляетсяпо правилам:
1.В левом столбцезаписываетсяноваябазиснаяпеременная(в нашем примере– x2 вместоx5.
2.Новуюстрокувместоразрешающейполучаютиз старойделением на разрешающийэлемент aij (в нашем примере он равен1).
3.В остальныхстроках,включаястрокуF, коэффициентыопределяются поправилупрямоугольника:староезначение в этойячейке,минус частное,в числителе– произведениеэлементов разрешающего столбцав данной строкеи разрешающейстрокив данном столбце.В знаменателе– значениеразрешающегоэлемента. Для нашего
примерапервыйсвободныйэлемент рассчитываетсяследующим |
|
образом: 18 – (3 * 5) / 1 = 3 |
12 |
Врезультате получается следующее базисное решение: x = (0, 5, 3, 11, 0, 21).
На рисунке оно показано следующей точкой:
0, 5, 3, 11, 0, 21
0, 0, 18, 16, 5, 21
3/1
11/2
∞
21/3
13
3, 5, 0, 5, 0, 21
Аналогичнонаходим следующеебазисное решение,эффективность последовательновозросла с0, затем15, сейчас– 21.
5/5
14
Критерийоптимальностивыполнен (внижней строкенет отрицательныхзначений), значениецелевой функции= 24, чтосовпадаетс полученным графическимспособом. Оптимальноерешение:
6, 4, 0, 0, 1, 3
15
ПРОБЛЕМА
Не всякая задача ЛП может быть решена непосредственным применением симплекс-метода. Для этого требуется, чтобы система фазовых ограничений содержала единичный базис, а целевая функция была выражена черезсвободныепеременные.
Поэтому, в общем случае для решения задачи ЛП, после ее приведения к канонической форме необходимо приведение ограничений к единичному базису, это возможно когда фазовые ограничения имеют
предпочтительныйвид.
16
РЕШАЕМЗАДАЧУ О ДИЕТЕ СИМПЛЕКСМЕТОДОМ
Обозначимчерез x1 и x2 количествокорма каждоговидасоответственно. С учетомстоимостикормов,целеваяфункциябудет иметьвид:
5x1 4x2 min |
5x1 4x2 max |
Ограниченияпо потребностив каждомэлементе выражены в следующейсистеме:
|
5x 3x |
|
255 |
|
5x |
3x |
|
|
x |
|
255 |
|
|
1 |
2 |
|
150 |
|
1 |
|
2 |
3 |
|
||
2.5x1 3x2 |
2.5x1 3x2 x4 150 |
|||||||||||
x 3.3x |
|
180 |
x 3.3x |
2 |
x |
4 |
180 |
|||||
|
1 |
2 |
|
|
|
1 |
|
|
|
|
||
Крометого,очевидно,что количествокормакаждоговидане может бытьотрицательнойвеличиной:
x1 0, x2 0 x1 0, x2 0, x3 0, x4 0, x5 17 0
МЕТОД ИСКУССТВЕННОГО БАЗИСА
1.В каждоеуравнение,дающее отрицательную компонентув базисном решении вводим новую
неотрицательнуюпеременнуюy1, y2, … yk, которая имееттот жезнак, что и свободныйчлен в правой части уравнения.
2.В симплекс-таблицу включаем и эти переменные.
3.Целевуюфункция заменяем функцией вида: T = F –
M(y1 + y2 + … + yk), где М – произвольноебольшое число.Благодаряэтому обозначениюполучилсвое второеназвание: M- метод.
18
ПЕРЕХОД ОТ КАНОНИЧЕСКОЙ К ПРЕДПОЧТИТЕЛЬНОЙ ФОРМЕ
5x1 4x2 max |
5x1 4x2 M(y1 y2 y3) max |
5x1 3x2 x3 255
2.5x1 3x2 x4 150x1 3.3x2 x5 180
x1 0, x2 0,
x3 0, x4 0, x5 0
|
5x |
3x |
|
|
x |
y |
255 |
|
1 |
|
2 |
3 |
1 |
|
|
2.5x1 3x2 x4 y2 150 |
|||||||
x 3.3x |
2 |
x |
y |
180 |
|||
|
1 |
|
|
5 |
3 |
|
|
x1 0, x2 0,
x3 0, x4 0, x5 0 y1 0, y2 0, y3 0
19
ПРЕОБРАЗОВАНИЕ ЦЕЛЕВОЙ ФУНКЦИИ
5x1 3x2 x3 y1 255
2.5x1 3x2 x4 y2 150
x1 3.3x2 x5 y3 180
8,5 x1 9,3 x2 x3 x4 x5 y1 y2 y3 585 8,5 x1 9,3 x2 x3 x4 x5 585 (y1 y2 y3)
5x1 4x2 M(y1 y2 y3) max
5x1 4x2 M( (8,5 x1 9,3 x2 x3 x4 x5 585)) max
20