183654 (743606), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

2. Рассмотрим ограничение (3) прямой задачи:

.

При введении искусственных переменных в целевую функцию вводятся коэффициенты штрафа М, поэтому для задачи максимизации получим:

.

Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак равенства, соответствуют двойственные переменные, не ограниченные в знаке .

3. Рассмотрим ограничение (4) прямой задачи:

В целевой функции избыточные переменные имеют коэффициенты, равные нулю ( ), а искусственные переменные коэффициенты, равные величине штрафа со своим знаком, в результате для задачи максимизации получим:

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

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

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

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

если переменная не ограничена в знаке, то ;

если , то .

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

После приведения ДЗ к стандартному виду используется симплекс - метод. Алгоритм получения решения тот же, что и для прямой задачи.

II. Практическая часть

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

Дана следующая задача линейного программирования (ЗЛП).

,

1.1. Все ограничения задачи .

1.2. Переменная ограниченна в знаке, поэтому . Переменная не ограничена в знаке, поэтому вводим замену , где .

Область допустимых решений будет ограничиваться I и IV квадрантом.

1.3. Построение ограничений и градиента целевой функции :

1.4. Область допустимых решений – отрезок AB.

1.5. Точка А – оптимальная. Координаты т. А:

; ; .

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

Прямая задача.

Задачу линейного программирования для любой вершины в компактной форме можно представить в виде:

Для получения используем алгоритм, приведённый в теоретической части.

1. Переход от неравенств к равенствам по правилам введения дополнительных переменных. Исходную задачу необходимо привести к стандартной форме: введем замену по переменной , и дополнительные переменные:

,

Полученный вид ЗЛП не позволяет сформировать начальный допустимый базис, т. к. нельзя выделить единичные орты во втором и третьем равенствах. Для получения начального допустимого базиса введём искусственные переменные. В результате получим:

,

2. Общее число переменных определим по формуле: =3+2+2=7, где - число искусственных переменных. Число базисных переменных определяется числом ограничений, т. к. , то система имеет три базисные переменные и небазисные переменные .

3. Получение - строки для СТ (0). Приведём целевую функцию к виду

.

Получим из (2): , из (3):

4. Формирование симплекс – таблицы на первом шаге:

Н ачальный базис

С Т (0) РС

									ПЧ
	1	-1-4M	3+3M	-3M-3	M	0	0	0	-12M
	0	1	2	-2	0	1	0	0	4
	0	3	-4	4	0	0	1	0	12
	0	1	1	-1	-1	0	0	1	0

5. Определение разрешающего столбца.

При решении задачи максимизации выбираем в - строке максимально отрицательный коэффициент: - включаемая переменная.

6. Определение разрешающей строки: – исключаемая переменная.

7. Разрешающий элемент РЭ = 1.

8. Получение матрицы перехода

, где В(0) - матрица перехода

9. Определение элементов таблицы СТ(1) = В(0) СТ(0);

10. Исследование z-строки СТ(1) на условие оптимальности:

С Т(1)

	z								ПЧ
z	1	0	4+7M	-7M-4	-3M-1	0	0	1+4M	-12M
	0	0	1	-1	1	1	0	-1	4
	0	0	-7	7	3	0	1	-3	12
	0	1	1	-1	-1	0	0	1	0

СТ(2)

	z								ПЧ
z	1	0	0	0	5/7	0	M+4/7	M-5/7	48/7
	0	0	0	0	10/7	1	1/7	-10/7	40/7
	0	0	-1	1	3/7	0	1/7	-3/7	12/7
	0	1	0	0	-4/7	0	1/7	4/7	12/7

Характеристики

Список файлов реферата