Задача 801

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

Постановка задачи

Найти неотрицательное решение ( все , j = 1,2, ..., n ) системы из уравнений :

( i = 1,2, ... ,m ), m > n (1)

образующее в максимум линейную целевую функцию :

(2)

Последовательность вычислений

1. Условия задачи записать в виде симплекс-таблицы размером (m+1) строка и (n+1) столбец:

			...
			...
			...
...	...	...	...	...	...
			...
z			...

(3)

Для размещения информации рекомендуется использовать массивы:
МАТР [ 1:(m+1)], 1:(n+1)] - для исходной матрицы ( симплекс-таблицы ),
X [1:n] - ( первоначально : -1, -2, ... , -n ),
Y[1:m] - ( первоначально : 1, 2, ... , m).

1. Алгоритм симплекс-метода состоит из двух основных этапов. На первом этапе отыскивается решение системы уравнений (1) и оно преобразуется в опорное решение, а далее на втором этапе целенаправленным переходом от одного опорного решения к другому получаем оптимальное решение, при этом в основе каждого из указанных этапов лежат модифицированные жордановы исключения ( МЖИ ). Суть их в следующем. Если мы имеем матрицу:

			...	-	...
=			...		...
...	...	...	...	...	...	...
			...		...
...	...	...	...	...	...	...
			...		...

(4)

то один шаг МЖИ с разрешающим элементом означает переход к новой матрице :

			...		...
=			...		...
...	...	...	...	...	...	...
			...		...
...	...	...	...	...	...	...
			...		...

(5)

где каждый элемент определяется:

Рекомендуется МЖИ оформить в виде процедуры. На каждом шаге МЖИ соответствующий элемент массива X меняется местом с соответствующим элементом массива Y.

1. Получение опорного решения.

1. Если все ( не считая строки z ), то опорное решение найдено. В этом случае все , а каждый ; идем на п.4. Если есть отрицательные свободные члены, переходим к п.3.2.

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

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

4. Осуществляем шаг МЖИ и возвращаемся к пункту 3.1.

1. Нахождение оптимального решения.

1. Проверка условия : решение оптимально. Если все , не считая , то получено оптимальное решение, в противном случае переходим к п.4.2.

2. Если < 0, то s-ый столбец берем в качестве разрешающего.

3. Проверка условия: задача имеет конечное решение. Если все , то линейная форма не ограничена снизу, задача не имеет конечного решения. В противном случае переходим к п.4.4.

4. Находим отношение свободных членов к положительным коэффициентам S-ого столбца и находим среди них наименьшее
   ,
   r-ую строку берем в качестве разрешающей, элемент будет разрешающим.

5. Осуществляем шаг МЖИ и возвращаемся к пункту 4.1.

1. После получения оптимального решения значения определяются с использованием массивов МАТР, X, Y.

Пример для отладки

Найти числа , максимизирующие функцию :

при ограничениях :

;

;

;

;

;

.

Решение.

	[1]	-1	10
	-1	1	20
	1	0	20
	0	1	10
	-1	0	0
	0	-1	0
z	-0,1	0,3	35
	1	-1	10
	1	0	30
	-1	1	10
	0	1	10
	1	-1	10
	0	-1	0
z	0,1	0,2	36

Получено оптимальное решение . Max z = 36 при = 10, = 0. т

Исходные данные для основного счёта

Найти max линейной формы :

,

при следующих ограничениях :

;

;

;

Результаты счета

1. Выдать на печать исходные данные, оптимальный план ( , , .... , )и значение линейной формы z.

2. Проанализировать полученный результат.