ЧМ-2

31

Поскольку коэффициент при x2 отрицателен, то и эта вершина не является оптимальной. Теперь мы должны увеличивать x2, положив x4=0. Из (7.17) имеем ограничения,

x2<50/(1/2)=100, x2<100/3=33.33, x2<60/2=30,

т.е. мы можем увеличить x2 до 30 и получить очередную вершину

x(2)1=35, x(2)2=30, x(2)3=10, x(2)4=0, x(2)5=0.

в этой вершине F = -710.

Теперь мы выбираем ненулевые переменные x1, x2, x3 в качестве базисных, и выражаем их через свободные переменные x4, x5. Из (7.14) получаем

4x1+ 5x2+ x3= 300

Вычитая из третьего уравнения второе, получаем

2x2=60+x4-x5, x2=30+0,5x4 - 0,5x5

Подставляя это все во второе уравнение, имеем

2x1= 100-x4-x2=100-x4-30-0,5x4+0,5x5=70-0,5*x4+0,5x5,

x1=35-0,75x4+0,25x5

Теперь первое уравнение дает

x3=300-4x1-5x2=300-140+3x4-x5-150-2.5*x4+2.5*x5=10+0,5x4+1,5x5,

Подставляя эти выражения в (7.15) находим

F=-10(35-0,75x4+0,25x5) -12(30+0,5x4 -0,5x5)= -710+1,5x4+3,5x5.

Здесь коэффициенты при x4, x5 положительны, т. е. найденная вершина есть точка минимума.

Итак, оптимальный план производства получается при x1=35, x2=30. Поскольку в исходной задаче две переменные, то ее можно было

решить графически.

Наше решение симплекс-методом соответствует движению по границе многоугольника из вершины A1(0,0) в вершину A2(50,0) и затем в вершину

A3(35,30).

7.3. Симплекс-таблица.

Все математические методы линейного программирования основаны на нахождении неотрицательных базисных решений. Итак, перед нами стоит

32

задача определения неотрицательного базисного решения. Пусть в системе линейных уравнений свободные члены всех уравнений - числа неотрицательные (в противном случае умножением обеих частей уравнения на -1 можно сделать свободный член положительным). Будем решать систему методом полного исключения переменных.

Исходная таблица:

Решение начинается с выбора разрешающего элемента. Сделаем это следующим образом:

1)за разрешающий столбец примем такой столбец, в котором имеется хотя бы один положительный элемент (Если все коэффициенты при переменных отрицательные, а свободные члены неотрицательные, то неотрицательное решение единственно: это (0,...,0));

2)пусть в разрешающем столбце несколько положительных элементов. Найдем отношения соответствующих свободных членов к этим элементам и за разрешающий элемент возьмем тот из них, для которого это отношение наименьшее (если в столбце один положительный элемент, то он и будет разрешающим). Затем осуществим пересчет элементов таблицы. Такое преобразование носит название симплексного.

Добавим, что если найдено хотя бы одно неотрицательное базисное решение, то с помощью симплексного преобразования можно перейти к другому неотрицательному базисному решению (если такое есть).

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

Алгоритм преобразования:

1)элементы разрешающей строки получаются из соответствующих элементов прежней строки делением на разрешающий элемент;

2)все элементы разрешающего столбца преобразованной таблицы, кроме разрешающего элемента, равны нулю;

3)все остальные элементы пересчитываются по правилу прямоугольника: выделяем прямоугольник в таблице 7.2 так, что элемент подлежащий пересчету (5), и разрешающий элемент (2) образуют одну из диагоналей. А затем из произведения этих элементов вычитаем произведение

33

элементов, образующих другую диагональ, и полученную разность делим на разрешающий элемент.

Пример. С помощью Симплекс-таблицы найти минимальное значение целевой функции (7.15):

F(x1,x2)= -f(x1,x2)= -10·x1- 12·x2- 0·x3 - 0·x4 - 0·x5 ® min

при данных ограничениях (7.14)

4·x1 + 5·x2 + x3 = 300 2·x1+ x2 + x4= 100 2·x1+ 3·x2+ x5= 160

x1,2,3,4,5³ 0

Решение. Коэффициенты при переменных переписываем в симплексные таблицы (Табл. 7.2). В данной задаче исходным базисным решением является: (0;0;300;100;160). Целевую функцию запишем в следующем виде:

F+10·x1+12·x2+0·x3+0·x4+0·x5 ® min.

Таблица 7.2

Разрешающий элемент таблицы есть а12=2. Для нахождения разрешающего элемента в столбце с положительным значением коэффициента целевой функций с1=10 выбираются положительные элементы a11=4, a12=2, а13=2; составляются отношения b1/a11=300/4, b2/a12=100/2 и b3/a13=160/2; из полученных отношений выбирается наименьшее.

34

Переменная х1 должна заменить в исходном базисе переменную х4. После соответствующих преобразований таблица будет иметь следующий вид:

В строке коэффициентов целевой функций F таблицы 7.3 элемент c2=7 положительный. Разрешающий элемент таблицы есть а23=2. Для нахождения разрешающего элемента в столбце выбираются положительные элементы a21=3, a22=0,5, а23=2; составляются отношения b1/a21=100/3, b2/a22=50/0,5 и b3/a23=60/2; из полученных отношений выбирается наименьшее. Переменная х2 должна заменить в исходном базисе переменную х5. После соответствующих преобразований таблица будет иметь следующий вид:

В строке коэффициентов целевой функции нет положительных элементов. Таблица 7.4 является последней в решении поставленной задачи. Из этой таблицы видно, что при базисном решении (35;30;10;0;0) целевая

35

функция F имеет значение F=-710. Значение F=-710 является наименьшим в данной задаче при x1=35, x2=30.

ЛИТЕРАТУРА

1.Калиткин Н.П. Численные методы. М.: Наука, 1978. - 512 с.

2.Солодовников А.С. Введение в линейную алгебру и линейное программирование. М.: Просвещение, 1966. - 183 с.

3.Химмельблау Д. Прикладное нелинейное программирование.

М.: Мир, 1975. - 534 с.

4. Попов В.И. Численные методы расчета мостовых конструкций на ЭВМ.

М.: 1981. - 78 с.

5.Монахов В.М. и др. Методы оптимизации. Применение математических методов в экономике. М., Просвещение, 1978. - 175 с.

6.Информатика. Методические указания к лабораторным работам. «Численные методы решения задач строительства на ЭВМ» для студентов специальности 2910.//Казанская государственная архитектурно-строительная академия; Сост.: Габбасов Ф.Г., Гатауллин И.Н., Киямов Х.Г. - Казань:, 1998.

-50 с.