Исследование операций и теория систем

L=21*200+15*100+30*100+23*100+10*200+12*100+21*200=18400

Проверим методом потенциалов:

Примем α1=0, тогда βj = cij – αi (для заполненных клеток).

Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0

Очевидно, что Δij =0 для заполненных клеток.

В результате получим следующую таблицу:

Таким образом, решение верное, т.к. Δij > 0 для всех пустых клеток и Δij =0 для всех заполненных.

Тогда сумма всех перевозок:

L=18400

Ответ:

Задача 4 (№53)

Условие:

Определить экстремум целевой функции вида

F = c11x12+c22x22+c12x1x2+b1x1+b2x2

при условиях:

a11x1+a12x2<=>p1

a21x1+a22x2<=>p2.

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

2. Составить функцию Лагранжа.

3. Получить систему неравенств в соответствии с теоремой Куна-Таккера.

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

5. Дать ответ с учетом условий дополняющей нежесткости.

Решение:

Целевая функция:

F= -2x12-x22-4x1x2+6x1+1,5x2→max

Ограничения g1(x) и g2(x): 2,5x1-x2³7 2,5x1-x2–7³0

3x1+2,5x2³13 3x1+2,5x2-13³0

1) определим относительный максимум функции, для этого определим стационарную точку (х10, х20):

→

2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции

F11 (х10, х20) = -4 < 0

F12 (х10, х20)=-4

F21 (х10, х20)=-4

F22 (х10, х20)=-2

F11 F12 -4 -4

F21 F22 -4 -2

Т.к. условие выполняется, то целевая функция является строго выпуклой в окрестности стационарной точки

3) Составляем функцию Лагранжа:

L(x,u)=F(x)+u1g1(x)+u2g2(x)=-2x12-x22-4x1x2+6x1+1,5x2+u1 (2,5x1-x2–7)+ u2 (3x1+2,5x2-13).

Получим уравнения седловой точки, применяя теорему Куна-Таккера:

i=1;2

Объединим неравенства в систему А, а равенства в систему В:

Система А:

Система В:

Перепишем систему А:

6-4x1-4x2+2,5u1+3u2 <0

1,5-4x1-2x2-u1+2,5u2 <0

2,5x1-x2–7³0

3x1+2,5x2–13³0

4)Введем новые переменные

V={v1,v2}≥0; W={w1,w2}≥0

в систему А для того, чтобы неравенства превратить в равенства:

6-4x1-4x2+2,5u1+3u2 + v1=0

1,5-4x1-2x2-u1+2,5u2 + v2=0

2,5x1-x2–7- w1=0

3x1+2,5x2–13- w2=0

Тогда

- v1=6-4x1-4x2+2,5u1+3u2

- v2=1,5-4x1-2x2-u1+2,5u2

w1=2,5x1-x2–7

w2=3x1+2,5x2–13

Следовательно, система В примет вид:

 Скачать реферат