Федеральное агентство связи

Сибирский Государственный Университет Телекоммуникаций и Информатики

Межрегиональный центр переподготовки специалистов

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

По дисциплине: Оптимизация и математические методы принятия решений

Выполнил:

Группа:

Вариант: 1

Проверил: ___________________

Новосибирск, 2012 г

Задача 1.1.1

Решите задачу о диете со следующими данными. Из продуктов трех видов необходимо составить рацион минимальной стоимости, соблюдя при этом ограничения по содержанию некоторых витаминов. Данные приведены в таблице:

	Продукты				Суточная потребность
	1	2	3
Е	3	2	1	14
F	3	4	5	10
РР	1	5	2	8
Цента продукта	8	12	11

Решение:

Обозначим через x₁ количество первого продукта, а через x₂ – количество второго продукта, x₃ – количество третьего продукта, включаемых в ежедневный рацион. Приходим к задаче:

Приведем систему неравенств к канонической форме путем введения дополнительных базисных переменных. В 1-м неравенстве вводим базисную переменную x₄ со знаком минус. В 2-м неравенстве вводим базисную переменную x₅ со знаком минус. В 3-м неравенстве вводим базисную переменную x₆ со знаком минус.

3x₁ + 2x₂ + x₃ – 1x₄ + 0x₅ + 0x₆ = 14

3x₁ + 4x₂ + 5x₃ + 0x₄ – 1x₅ + 0x₆ = 10

x₁ + 5x₂ + 2x₃ + 0x₄ + 0x₅ – 1x₆ = 8

Умножим все строки на (-1) и будем искать первоначальный опорный план.

–3x₁ – 2x₂ – x₃ + 1x₄ – 0x₅ – 0x₆ = –14

–3x₁ – 4x₂ – 5x₃ – 0x₄ + 1x₅ – 0x₆ = –10

–x₁ – 5x₂ – 2x₃ – 0x₄ – 0x₅ +1x₆ = –8

Введем новую переменную x₀ = –8x₁–12x₂–11x₃.

Выразим базисные переменные <4, 5, 6> через небазисные.

x₀ = 0-8x₁-12x₂-11x₃ x₄ = -14+3x₁+2x₂+x₃

x₅ = -10+3x₁+4x₂+5x₃ x₆ = -8+x₁+5x₂+2x₃

Среди свободных членов в системе уравнений есть отрицательные элементы. Используем двойственный симплекс-метод. Выберем из них наибольший по модулю, а в его уравнении – любой отрицательный.

Чтобы теперь выразить все переменные через небазисные, в выражении для x₄ выразим x₁ и подставим полученное выражение во все остальные равенства.

x₀ = -37,33-6,67x₂-8,33x₃-2,67x₄ x₁ = 4,67-0.67x₂-0,33x₃+0,33x₄

x₅ = 4+2x₂+4x₃+x₄ x₆ = -3,33+4,33x₂+1,67x₃+0,33x₄

Среди свободных членов в системе уравнений есть отрицательные элементы. Используем двойственный симплекс-метод. Выберем из них наибольший по модулю, а в его уравнении – любой отрицательный.

Чтобы теперь выразить все переменные через небазисные, в выражении для x₆ выразим x₂ и подставим полученное выражение во все остальные равенства.

x₀ = -42,46-5,77x₃-2,15x₄-1,54x₆

x₁ = 4,15-0,0769x₃+0,38x₄-0,15x₆

x₅ = 5,54+3,23x₃+0,85x₄+0,46x₆

x₂ = 0,77-0,38x₃-0,0769x₄+0,23x₆

В базисном столбце все элементы положительные. Переходим к основному алгоритму симплекс-метода. Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x₀. Выражение для x₀ не содержит положительных элементов. Найден оптимальный план.

Окончательный вариант системы уравнений:

x₀ = -42,46-5,77x₃-2,15x₄-1,54x₆

x₁ = 4,15-0,0769x₃+0,38x₄-0,15x₆

x₅ = 5,54+3,23x₃+0,85x₄+0,46x₆

x₂ = 0,77-0,38x₃-0,0769x₄+0,23x₆

Оптимальный план можно записать так:

x₁ = 4,15 x₅ = 5,54 x₂ = 0,77

F(X) = 8*4,15 + 12*0,77 = 42,46

Стоимость рациона не может быть меньше, чем 42,46 денежных единиц.

Задача 1.1.5

Приведите следующие задачи к каждой из канонических форм, описанных в лекции:

Решение:

1. В задаче №1 одно из ограничений задано в виде равенства, а другое – в виде неравенства.

Запишем условие в виде пары неравенств: и .

Второе неравенство умножением на –1 приведём к виду .

Получаем каноническую форму задачи на максимум, в которой все ограничения заданы в виде неравенств вида ≤:

Каноническую форму задачи на минимум, в которой все ограничения заданы в виде неравенств вида ≥, получим, умножая целевую функцию и каждое неравенство на –1:

Каноническую форму задачи, в которой все ограничения заданы в виде равенств, получим, введя новую неотрицательную переменную z:

или

2. Для приведения задачи к канонической форме необходимо:

Привести целевую функцию к минимизации умножением на (-1)

3. Т.к. переменные x₂ и x₃ могут принимать как положительные, так и отрицательные значения, заменим их разностями новых неотрицательных переменных.

Т.к. , т.е. можно ввести только 2 новые переменные х₄ и х₅:

и .

Тогда целевая функция будет иметь вид:

Ограничение заменится на .

Записываем для этой задачи канонические формы:

Задача 1.2.1

Докажите лемму 1, следствие из нее и признак оптимальности в краткой форме:

Лемма 1. При любых  и   выполняется неравенство

                                                           

Важным является прямое следствие этой леммы, которое позволяет сформулировать и признак оптимальности в самой простой форме.

Следствие. Если    и    таковы, что ,

то х° — оптимальный вектор в исходной задаче, а у° — в двойственной.

Доказательство.

Введем вектор переменных прямой задачи и вектор переменных двойственной задачи .

Записываем прямую задачу:

– целевая функция прямой задачи;

все ограничения запишем в виде неравенств: , i =1,2,…m.

Записываем двойственную задачу:

– целевая функция двойственной задачи;

все ограничения запишем в виде неравенств: , j =1,2,…n.

Умножим каждое i-тое неравенство системы ограничений прямой задачи на переменную y_i и сложим правые и левые части полученных неравенств.

Получим: .

Аналогично, умножим каждое j-тое неравенство системы ограничений двойственной задачи на переменную x_j и сложим правые и левые части полученных неравенств.

Получим: .

Левые части неравенств представляют собой одно и то же выражение.

Поэтому можно записать двойное неравенство: .

Т.к. и , получаем требуемое неравенство:.

Следствие из леммы 1. Если и таковы, что , то х° – оптимальный вектор в исходной задаче, а у° – в двойственной.

Доказательство:

Согласно доказанной лемме 1 при любых допустимых решениях прямой и двойственной задачи и выполняется неравенство .

Т.к. для векторов х° и у° выполняется равенство , то х° – вектор в исходной задаче, при котором достигается наименьшее значение функции , а у° – вектор в двойственной задаче, при котором достигается наибольшее значение функции . Следовательно, х° – оптимальный вектор в исходной задаче, а у° – в двойственной.

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

Доказательство.

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

Следовательно, значение целевой функции на любом допустимом векторе прямой задачи больше или равно значению целевой функции на векторе , т.е. на векторе значение целевой функции минимально. Отсюда следует, что вектор х° – оптимальный вектор в прямой задаче.