Исследование операций (стр. 3 из 3)

A2)

перепишем систему Б:

Б2)

- условия дополняющей нежёсткости

Решим систему А2 с помощью метода искусственных переменных.

в первое и второе уравнение системы А2.

Вводим псевдоцелевую функцию

базисные переменные: y1, y2, w1, w2

свободные переменные: x1, x2, v1, v2, u1, u2

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

Таблица 12

bi	x1	x2	u1	u2	v1	v2
y1	1 0.5	2 0.5	-0.5 -0.25	1 0.5	0 0	-1 -0.5	0 0
y2	8 0.25	-0.5 0.25	2 -0.125	1 0.25	1 0	0 -0.25	-1 0
w1	7 -0.5	1 -0.5	1 0.25	0 -0.5	0 0	0 0.5	0 0
w2	5 0	0 0	1 0	0 0	0 0	0 0	0 0
Y'	9M 0.75M	-1.5M 0.75M	-1.5M -0.375M	-2M 0.75M	-1M 0M	1M -0.75M	1M 0M

Таблица 13

bi	y1	x2	u1	u2	v1	v2
x1	0.5 1.1	0.5 0.03333	-0.25 0.1333	0.5 0.1667	0 0.1333	-0.5 -0.03333	0 -0.1333
y2	8.25 4.4	0.25 0.1333	1.875 0.5333	1.25 0.6667	1 0.5333	-0.25 -0.1333	-1 -0.5333
w1	6.5 -5.5	-0.5 -0.1667	1.25 -0.6667	-0.5 -0.8333	0 -0.6667	0.5 0.1667	0 0.6667
w2	5 -4.4	0 -0.1333	1 -0.5333	0 -0.6667	0 -0.5333	0 0.1333	0 0.5333
Y'	9.75M 8.25M	0.75M 0.25M	-1.875M 1M	-1.25M 1.25M	-1M 1M	0.25M -0.25M	1M -1M

Таблица 14

bi	y1	y2	u1	u2	v1	v2
x1	1.6	0.5333	0.1333	0.6667	0.1333	-0.5333	-0.1333
x2	4.4	0.1333	0.5333	0.6667	0.5333	-0.1333	-0.5333
w1	1	-0.6667	-0.6667	-1.333	-0.6667	0.6667	0.6667
w2	0.6	-0.1333	-0.5333	-0.6667	-0.5333	0.1333	0.5333
Y'	18M	1M	1M	0M	0M	0M	0M

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

y1=y2=u1=u2=v1=v2=0

x1=1.6

x2=4.4

w1=1

w2=0.6

Проверим условие дополняющей нежёсткости:

xi*vi=0

ui*wi=0

Условия выполняются, следовательно, x1=1.6, x2=4.4 являются решением исходной задачи kвадратичного программирования. Координаты стационарной точки совпадают с координатами, полученных в качестве ответа. Стационарная точка удовлетворяет условиям ограничений.

Значение функции в точке (x1;x2) равно 0.

Ответ:

x1=1.6

x2=4.4

f(x1;x2) = 0

Приложение 1

Для решения задачи #4 использована следующая программа на языке Си, скомпилированная gcc (GCC) 4.0.0 20050519 (Red Hat 4.0.0-8). Её текст приведён ниже:

#include <stdio.h>

#define x 7

#define y 5

double mc[x*y] =

{

1, 2, -0.5, 1, 0, -1, 0,

8, -0.5, 2, 1, 1, 0, -1,

7, 1, 1, 0, 0, 0, 0,

5, 0, 1, 0, 0, 0, 0,

9, -1.5, -1.5, -2, -1, 1, 1

};

double mt[x*y];

void mprint (double* m, int xs, int ys)

{

int i, j;

printf ("&bsol;n");

for (j = 0; j < ys; j++)

{

for (i = 0; i < xs; i++)

{

printf ("%10.4lg ", m[j*xs+i]);

}

printf ("&bsol;n");

}

}

int main (void)

{

int i, j, i1, j1, it, jt;

double msx, msx1;

// Выбираем разрешающий эл-т

nextmtx:

printf ("&bsol;nИсходная матрица коэффициентов:"); mprint (mc, x, y);

getch ();

msx = 10000.;

for (i = 0; i < x; i++)

{

if (mc[(y-1)*x+i] < 0)

{

// Возможно, найден разрешающий столбец

for (j = 0; j < y; j++)

{

// Ищем наименьшее отношение своб. члена к эл-ту разр. столбца

if (mc[j*x+i] < 1e-32)

continue; // Нулевой или отрицательный

msx1 = mc[j*x] / mc[j*x+i];

if (msx > msx1) // Частное св.ч / р.эл

{

msx = msx1; // наименьшее ищем

it = i; jt = j; // координаты р.эл.

}

}

if (msx > 9999.) continue; // Нет положительных эл-тов

else // найден р.эл., mx != 0

{

i = it; j = jt; // его координаты

}

printf ("&bsol;n Разрешающий элемент: a(%d;%d) = %lg", j+1, i+1, mc[j*x+i]);

if (mc[j*x+i] > 0)

{

// Это и есть разрешающий элемент (s_el), находим обратную величину

mt[j*x+i] = 1. / mc[j*x+i];

for (i1 = 0; i1 < x; i1++)

{

// Разрешающая строка ( 1/s_el)

if (i1 == i) continue; // Пропустить сам s_el

mt[j*x+i1] = mt[j*x+i] * mc[j*x+i1];

}

for (j1 = 0; j1 < y; j1++)

{

// Разрешающий столбец (-1/s_el)

if (j1 == j) continue; // Пропустить сам s_el

mt[j1*x+i] = - mt[j*x+i] * mc[j1*x+i];

}

// успешно составлены разр. строка и столбец.

// теперь составляем остальные коэфф-ты

for (j1 = 0; j1 < y; j1++)

{

if (j1 == j) continue; // Пропустить всю разреш. строку

for (i1 = 0; i1 < x; i1++)

{

if (i1 == i) continue; // И столбец тоже

// Произведение нижней части столбца

// на верхнюю часть строки

mt[j1*x+i1] = mt[j1*x+i] * mc[j*x+i1];

}

}

/*

* Всё. Готова матрица нижних значений, теперь нужно

* поместить всё на свои места в mc

*/

printf ("&bsol;nМатрица нижних значений:"); mprint (mt, x, y);

getch ();

for (j1 = 0; j1 < y; j1++)

{

for (i1 = 0; i1 < x; i1++)

{

if ((j1 == j) || (i1 == i))

{

/*

* Разрешающая строка или столбец

* просто ложим элементы в mc

*/

mc[j1*x+i1] = mt[j1*x+i1];

}

else

// иначе - сумму

mc[j1*x+i1] += mt[j1*x+i1];

}

}

// Всё готово к очередному шагу.

goto nextmtx; // след. матрица

}

// Этот эл-т не подходит, т.к. он отрицательный

}

// Если так и не было подходящего эл-та, то проверяем след. столбец

}

// отрицательны коэфф-тов при целевой ф-ции не найдено, следовательно, решение оптимально

printf ("&bsol;nОптимизировано. Ответ:"); mprint (mc, x, y);

return 0;

}

Программа компилировалась командной строкой:

gcc simplex.c -o simplex

, запускалась:

./simplex

и выдавала на консоль пошаговое решение задачи, которое было занесено в симплекс-таблицы (см. табл. 12-14) четвёртой задачи данной курсовой работы.

Список использованной литературы

1. Кремер Н. Ш., Путко Б. А., Трощин И. М. «Исследование операций в экономике» - М.: ЮНИТИ, 2004. - 407 с.

2. Плотникова Н. В. Курс лекций (ПС)