Министерство образования республики Беларусь

Учреждение образования

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ»

Институт информационных технологий

Специальность ИТИуТС

Контрольная работа

По курсу «Математические основы теории систем»

Вариант № 18

Студент-заочник 2 курса

Группы № 082424

ФИО Милашевский

Владимир Сергеевич

Адрес г. Минск

Ул. Рогачевская 5-20

Тел. [phone]

Минск, 2012

Содержание:

1) Задание 1: Линейное программирование……………………………………..3

2) Задание 2: Нелинейное программирование…………………………………14

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

Задание 1: Линейное программирование

1. Найти оптимальный план x* и экстремальное значение функции F(x).

2. Построить задачу, двойственную к исходной, решить её и сравнить решения прямой и двойственной задач.

3. Если решение не является целочисленным, получить целочисленное решение путём введения дополнительных ограничений по методу Гомори.

Вариант 18.

Условия задачи: F(x) = 3x₁ + x₂ -6x₃ (max)

1. Математическая модель выглядит следующим образом:

max{F(x) = 3x₁ + x₂ - 6x₃ | -6x₁ - x₂ - 6x₃ ≥ -39; 2x₁ - 3x₂ + 5x₃ ≤ 12;

-x₁ + 5x₂ + 4x₃ ≤ 24; x_1,2,3 ≥ 0}.

Для удобства заполнения симплекс-таблицы приведем ограничения к виду «≤», умножив обе части неравенства на «-1».

Приведем ограничения к виду равенств, введя дополнительные переменные со знаком «+», т.к. ограничения вида «≤»:

Матрицы A, Bи C^Tвыглядят следующим образом:

A=;B = ;С^T = ;

Если дополнительная переменная со знаком «-», то все коэффициенты перед переменными x_i и свободный член b_j заносятся с противоположным знаком.

Если цель минимизация, то коэффициенты функции цели заносятся без изменения знака.

Симплекс-таблица выглядит следующим образом:

БП	СЧ	НП
		x1	x2	x3
x4 x5 x6	39 12 24	6 2 -1	1 -3 5	6 1 4
Fmax	0	-3	-1	6

За базисные переменные принимаем дополнительные переменные x₄, x₅,x₆. А переменные x₁, x₂,x₃ будут являться небазисными.

Свободные члены определяют решение задачи.

1 шаг: Производится поиск базисного решения. Т.к. все свободные члены положительны, значит, решение является допустимым. Переходим сразу к шагу 5 для нахождения оптимального решения.

5 шаг: Признаком оптимальности является неотрицательность переменных в F-строке. c₁, c₂ < 0. Следовательно, решение не является оптимальным.

В базис будет включаться та из небазисных переменных, которая находится в столбце с элементом c_l, которому соответствует максимальное абсолютное значение.

В данной задаче это элемент c₁ = -3< 0.Ведущий столбец x₁.

Выбор ведущей строки определяется минимальным симплексным отношением . Следует рассматривать только положительные симплексные отношения.

В данной задаче минимальное симплексное отношение получается в строке

x₅ = 6.

Таким образом, ведущая строка x₅. Ведущий элемент a₂₁ = 2.

Производим пересчет симплекс-таблицы:

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

Новая симплекс-таблица выглядит следующим образом:

БП	СЧ	НП
		x5	x2	x3
x4 x1 x6	3 6 30	-3	10	3
Fmax	18

БП	СЧ	НП
		x5	x4	x3
x2 x1 x6
Fmax

БП	СЧ	НП
		x6	x4	x3
x2 x1 x5
Fmax

F_max = .

Оптимальный план:

x₂ =

x₁ =

x₅ =

2. Выводим условия двойственной задачи:

F(x) = 3x₁ + x₂ -6x₃ (max)

Так как задача максимизации, то условия приводим к виду «≤»:

Матрицы A^T, Bи Cвыглядят следующим образом:

A^T= ;B = ;С =;

Количество переменных в двойственной задаче равно количеству переменных в прямой, и наоборот.

Тогда A^TY ≥ C примет вид:

Функция цели F(y) = B^TY = = 39y₁ + 12y₂ + 24y₃ (min)

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

Далее решение производится симплекс-методом.

Вводим дополнительные переменные и приводим ограничения к виду равенств.

Так как цель минимизация, коэффициенты функции цели заносятся в таблицу без изменения знака.

БП	СЧ	НП
		y1	y2	y3
y4 y5 y6	-3 -1 6	-6 -1 -6	-2 3 -5	1 -5 -4
Fmin	0	39	12	24

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

Производим поиск допустимого базисного решения, используя шаг 2.

2шаг: Производим пересчет симплекс-таблицы:

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

Пусть это будет b₁= -3 < 0.Просматриваем строку, в которой находится этот элемент, и выбираем любой отрицательный элемент.

Пусть это будет a₁₁ = -6 < 0.

Если в строке нет отрицательных элементов, то задача не имеет решения.

Приоритетом в выборе элементов является максимальное абсолютное значение модуля элемента.

Таким образом, ведущим элементом будет являться элемент a₁₁ = -6. Ведущая строка y₄, ведущий столбец – y₁. Из базиса исключается переменная y₄, в базис вводится переменная y₁.

Производим пересчет симплекс-таблицы.

Новая симплекс-таблицы выглядит следующим образом:

БП	СЧ	НП
		y4	y2	y3
y1 y5 y6	9	-1	-3	-5
Fmin			-1

БП	СЧ	НП
		y4	y2	y5
y1 y3 y6
Fmin

Оптимальное решение найдено.

F_min = .

Оптимальный план:

y₁ = .

y₃ = .

y₆ = .

Решения прямой и двойственной задачи совпадают.

Решение задачи без условия целочисленности приведено в пункте 1.

Составим дополнительное ограничение по строке, соответствующей переменной x₂, так как у неё наибольшая дробная часть {x₂} = .

Решение производим по алгоритму Гомори для полностью целочисленной задачи.

x₆ +x₄ +x₃ ≥

или

x₆ +x₄ +x₃ ≥

Приведем к виду равенства, введя дополнительную переменную x₇ и домножим обе части неравенства на «-1»:

x₆ x₄ x₃ +x₇ = -

Расширенная симплекс-таблица выглядит следующим образом:

БП	СЧ	НП
		x6	x4	x3
x2 x1 x5 x7
Fmax

БП	СЧ	НП
		x7	x4	x3
x2 x1 x5 x6	5	1	0	0 0 -1 5
Fmax	22