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

Таблица 5

B1	B2	B3	ai
A1	10	20	32	700
A2	12	50	25	600
A3	21	18	50	200
A4	25	15	23	200
A5	21	30	40	100
bj	300	700	1000

Решение

Заметим, что общее количество запасов (700+600+200+200+100=1800) меньше количества заявок (300+700+1000=2000), следовательно имеем открытую транспортную задачу с избытком заявок. Добавим строку с фиктивными запасами для дополнения задачи до задачи закрытого типа. После корректировки получаем транспортную задачу с правильным балансом (табл. 6):

Таблица 6

B1	B2	B3	ai
A1	10	20	32	700
A2	12	50	25	600
A3	21	18	50	200
A4	25	15	23	200
A5	21	30	40	100
A6	0	0	0	200
bj	300	700	1000	2000

Найдём опорное решение методом наименьших затрат (табл. 7):

Таблица 7

B1	B2	B3	ai
A1	10 300	20 400	32 -	700	-10 (2)
A2	12 -	50 -	25 600	600	-7 (7)
A3	21 -	18 200	50 -	200	-8 (4)
A4	25 -	15 100	23 100	200	-5 (5)
A5	21 -	30 -	40 100	100	-22 (8)
A6	0 -	0 -	0 200	200	18 (9)
Bj	300	700	1000	2000
0 (1)	-10 (3)	-18 (6)

Выбранный план перевозок является допустимым, т.к. при нём все заявки удовлетворены и все запасы израсходованы, сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу – заявке соответствующего пункта назначения. Сумма запасов равна сумме заявок, и выражается числом 2000, стоящим в правом нижнем углу таблицы. Данное распределение является базисным (заполнено m+n-1=8 ячеек таблицы), следовательно, задача готова к решению.

Первоначально затраты на перевозку составят:

Составим матрицу оценок методом потенциалов:

Начнём с первого столбца. Пусть потенциал этого столбца равен нулю. Рядом с потенциалом в скобках записываем номер шага. После прибавления потенциала к коэффициентам затрат первого столбца коэффициент затрат заполненной клетки (1;1) не изменится; чтобы полученный после сложения коэффициент стал равен 0, потенциал первой строки таблицы должен быть равен -10; для обнуления коэффициента затрат клетки (1;2) потенциал второго столбца должен быть -10 и т.д.

Изменённые коэффициенты выписываются в виде матрицы оценок:

Критерий оптимальности (базисное распределение поставок верно тогда и только тогда, когда оценки всех свободных клеток неотрицательны) на данном шаге не выполнен – присутствуют 2 свободные клетки с отрицательными оценками.

Продолжим оптимизацию (табл. 8). Составим цикл пересчёта для клетки (5;2) и дадим поставку неё:

Таблица 8

B1	B2	B3	ai
A1	10 300	20 400	32 -	700
A2	12 -	50 -	25 600	600
A3	21 -	18 200	50 -	200
A4	25 -	15 - 100	23 + 100	200
A5	21 -	30 + -	40 - 100	100
A6	0 -	0 -	0 200	200
Bj	300	700	1000	2000

В верхнем правом углу знаком «+» отмечаются те клетки, поставки в которые увеличатся, а знаком «-» - те, в которые уменьшатся. Наибольшая возможная поставка, исходя из текущего цикла пересчёта равна min {100, 100, 100} = 100. Передвигаем её по циклу (табл. 9):

Таблица 9

B1	B2	B3	ai
A1	10 300	20 400	32 -	700	-10 (2)
A2	12 -	50 -	25 600	600	-7 (8)
A3	21 -	18 200	50 -	200	-8 (4)
A4	25 -	15 0	23 200	200	-5 (5)
A5	21 -	30 100	40 -	100	-20 (6)
A6	0 -	0 -	0 200	200	18 (9)
Bj	300	700	1000	2000
0 (1)	-10 (3)	-18 (7)

После передвижения освободились сразу 2 клетки, решение перестало быть базисным. Для того, чтобы оно осталось базисным, дадим фиктивную поставку в клетку (4;2).

Снова составляем матрицу оценок по вышеприведённому алгоритму:

На текущем шаге клеток с отрицательной оценкой нет, следовательно, критерий оптимальности выполнен.

Проверим решение с помощью метода потенциалов (табл. 10). Примем a1 = 0, тогда bj = cij – ai (для заполненных клеток). Если найденное решение справедливо, то во всех пустых клетках таблицы Δij = cij – (ai + bj ) ≥ 0, и Δij = 0 в заполненных клетках. Получим следующую таблицу (в скобках показаны оценки клеток):

Таблица 9

B1	B2	B3	ai
A1	10 (0) 300	20 (0) 400	32 (4) -	700	-10 (2)
A2	12 (5) -	50 (33) -	25 (0) 600	600	-7 (8)
A3	21 (13) -	18 (0) 200	50 (24) -	200	-8 (4)
A4	25 (20) -	15 (0) 0	23 (0) 200	200	-5 (5)
A5	21 (1) -	30 (0) 100	40 (2) -	100	-20 (6)
Bj	300	700	1000
0 (1)	-10 (3)	-18 (7)

Условие Δij ≥ 0 выполняется, следовательно, решение верное.

Ответ:

Таблица 10

B1	B2	B3	ai
A1	10 300	20 400	32 -	700
A2	12 -	50 -	25 600	600
A3	21 -	18 200	50 -	200
A4	25 -	15 -	23 200	200
A5	21 -	30 100	40 -	100
Bj	300	700	1000	1800/2000

Суммарные затраты на перевозку составляют:

Задача 4

Условие

Решение задачи нелинейного программирования

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

F = c11x12+c22x22+c12x1x2+b1x1+b2x2

при условиях

a11x1+a12x2<=>p1

a21x1+a22x2<=>p2 .

Данные располагаются в табл. 11.

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

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

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

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

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

Таблица 11

b1	b2	c11	c12	c22	extr	a11	a12	a21	a22	p1	p2	Знаки огр.
												1	2
1	8	-1	0.5	-1	max	1	1	0	1	7	5	≤	≤

Решение

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

Ограничения:

,

1. Определим относительный максимум функции. Для этого необходимы координаты стационарной точки

.

,

Получили стационарную точку (1.6;4.4).

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

,

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

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

Составим систему неравенств в соответствии с теоремой Куна-Таккера.

А)

Б)

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

A1)

.Вводим дополнительные переменные v1, v2, w1, w2, превращающие неравенства системы А1 в равенства: