Решение двойственной задачи
Определение затрат на осуществление связи при имеющихся параметрах кабелей. Построение вектора-градиента, составленного из коэффициентов целевой функции. Нахождение оптимального решения двойственной задачи по теореме равновесия. Метод идеальной точки.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 31.03.2015 |
| Размер файла | 130,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Федеральное агентство связи
Сибирский Государственный Университет Телекоммуникаций и Информатики
Межрегиональный центр переподготовки специалистов
Контрольная работа
По дисциплине:
"Методы оптимальных решений"
Выполнил: Тарасова Т.В. Группа: ФКТ-32
Новосибирск, 2015
Задача 1
Решить графически задачу из лабораторной работы №1.
Решение
Введем переменные: x1 - количество кабеля типа I, x2 - количество кабеля типа II. По определению эти переменные должны быть неотрицательны. При связи, использующей x1 кабелей I типа и x2 кабелей II типа, могут использоваться 5x1+x2 телефонных каналов, 5x1+4x2 телеграфных каналов и 2x1+5x2 фототелеграфных каналов. Для осуществления связи необходимо наличие не менее требуемого количества каналов. Получаем ограничения на количества имеющихся каналов:
Затраты на осуществление связи, имеющей x1 кабелей I типа и x2 кабелей II типа, составят: (11x1+x2)1000=11000x1+1000x2 условных единиц. Получаем математическую модель задачи:
5x1+x2?12
5x1+4x2?33
2x1+5x2?20
x1; x2?0, целое.
P(x)=11000x1+1000x2?min
5x1+x2?12 x2?12-5x1
5x1+4x2?33 x2?33/4-5x1/4
2x1+5x2?20 x2?4-2x1/5
x1; x2?0, целое. x1; x2?0, целое.
Первое неравенство системы ограничений задачи x2?12-5x1 описывает полуплоскость, лежащую выше прямой x2=12-5 x1, которую строим по точкам (1;7) и (2;2).
Второе неравенство системы ограничений задачи x2?33/4-5x1/4 описывает полуплоскость, лежащую выше прямой x2=33/4-5x1/4, которую строим по точкам (1;28/4) и (2;23/4).
Третье неравенство системы ограничений задачи x2?4-2x1/5 описывает полуплоскость, лежащую выше прямой x2=4-2x1/5, которую строим по точкам (1;18/5) и (2;16/5).
Неограниченная сверху область ABC - множество допустимых решений системы ограничений задачи.
Строим линию уровня , т.е. 11000x1+1000x2=0 x2=-11x1
Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора - точка (0; 0), конец - точка (11000; 1000). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области.
Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых 5x1+x2=12 и x1=0, найдем ее координаты, решив систему уравнений:
5x1+x2=12
x1=0
Решив систему уравнений, получим: x1 = 0, x2 = 12
Откуда найдем минимальное значение целевой функции:
F(X) = 11000*0 + 1000*12 = 12000
Задача 2
Составить двойственную задачу к задаче 1. Найти ее решение по теореме равновесия.
Решение. Составим двойственную задачу к данной
5x1+x2?12
5x1+4x2?33
2x1+5x2?20
x1; x2?0, целое.
5y1+5y2+2y3?11000
y1+4y2+5y3?1000
y1; y2; y3?0
F=12y1+33y2+20y3>max
Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости
y1(5x1+x2-12)=0
y2(5x1+4x2-33)=0
y3(2x1+5x2-20)=0
x1(5y1+5y2+2y3-11000)=0
x2(y1+4y2+5y3-1000)=0
Подставим в составленную систему оптимальное решение исходной задачи Xопт=(0;12):
y1(5*0+12-12)=0
y2(5*0+4*12-33)=0
y3(2*0+5*12-20)=0
x1(5y1+5y2+2y3-11000)=0
x2(y1+4y2+5y3-1000)=0
y1(0+0)=0
y2(0+33-33)=0
y3(0+60-20)=0
x1(5y1+5y2+2y3-11000)=0
x2(y1+4y2+5y3-1000)=0
y1*0=0;
y2*0=0
y3*40=0; y3=0
x1(5y1+5y2+2y3-11000)=0
x2(y1+4y2+5y3-1000)=0
Тогда
x1(5y1+5y2+2*0-11000)=0
x2(y1+4y2+5*0-1000)=0
0(5y1+5y2-11000)=0
12(y1+4y2-1000)=0
5у1=1000-5у2; у1=200-у2.
12(200-у2)+60у2-12000=0, 48у2=9600, у2=200, у1=0.
Оптимальное решение двойственной задачи
F=12y1+33y2+20y3=12*0+33*200+20*0=6600
Задача3
Решить двухкритериальную задачу линейного программирования методом идеальной точки.
решение двойственный равновесие точка
Решение:
OABCD - область допустимых решений системы ограничений задачи.
y=4+x/2 y=4 A(0;4)
x=0 x=0
y=18-3x 18-3x=4+x/2 7x/2=14 x=4 B(4;6)
y=4+x/2 y=4+x/2 y=4+x/2 y=6
y=18-3x 18-3x=3x/2-9/2 9х=45 x=5 C(5;3)
y=3x/2-9/2 y=3x/2-9/2 y=3x/2-9/2 y=3
y=3x/2-9/2 x=3 D(3;0)
y=0 y=0
Рассмотрим преобразование
В этом случае,
O(0;0)>O'(0;0); A(0;4) >A'(12;-4); B(4;6) >B'(-18;-2);
C(5;3)>C'(-36;2); D(3;0) >D'(-27;3)
Точка утопии М*(12,3) - точка, в которой первая и вторая координаты новых точек принимают максимальные значения.
Граница Парето пятиугольника О` A`B`C`D` состоит из отрезков O`D` и О`A`.
Найдем уравнение прямой, проходящей через точки O'(0;0) и A'(12;-4):
Найдем уравнение прямой L, перпендикулярной прямой O`A` и проходящей через точку М:
Таким образом, уравнение искомой прямой имеет вид:.
Найдем точку пересечения полученных перпендикулярных прямых, решив систему из соответствующих уравнений:
v=15.75
u=6.75
Находим соответствующие значения x и y:
x=40.5
y=24.75
Размещено на Allbest.ru
...Подобные документы
Геометрический смысл решений неравенств, уравнений и их систем. Определение понятия двойственности с помощью преобразования Лежандра. Разбор примеров нахождения переменных или коэффициентов при неизвестных в целевой функции двойственной задачи.
дипломная работа [2,6 M], добавлен 30.04.2011Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
курсовая работа [219,4 K], добавлен 17.04.2013Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
контрольная работа [333,3 K], добавлен 27.11.2011Графический и симплексный методы решения ОЗЛП. Построение функции цели, образующая совместно с системой ограничений математическую модель экономической задачи. Нахождение неотрицательного решения системы линейных уравнений. Решение транспортной задачи.
лабораторная работа [322,9 K], добавлен 10.04.2009Общая схема методов спуска. Метод покоординатного спуска. Минимизация целевой функции по выбранным переменным. Алгоритм метода Гаусса-Зейделя. Понятие градиента функции. Суть метода наискорейшего спуска. Программа решения задачи дискретной оптимизации.
курсовая работа [90,8 K], добавлен 30.04.2011Формирование нижних и верхних оценок целевой функции. Алгоритм метода ветвей и границ, решение задач с его помощью. Решение задачи коммивояжера методом ветвей и границ. Математическая модель исследуемой задачи, принципы ее формирования и порядок решения.
курсовая работа [153,2 K], добавлен 25.11.2011Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Структура текстовой задачи. Условия и требования задач и отношения между ними. Методы и способы решения задач. Основные этапы решения задач. Поиск и составление плана решения. Осуществление плана решения. Моделирование в процессе решения задачи.
презентация [247,7 K], добавлен 20.02.2015Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012Нахождение производных заданной функции. Частные производные первого и второго порядка. Вычисление неопределенных интегралов. Решение задачи комбинаторики. Расчет коэффициентов прямых материальных затрат с помощью межотраслевого балансового метода.
контрольная работа [359,1 K], добавлен 15.04.2013Понятие кватернионов: свойства, замена матрицами, геометрическая и тригонометрическая интерпретации. Изучение обтекания кругового цилиндра в идеальной жидкости, создание программы для визуализации задачи, ее решение в комплексной форме в квартернионах.
курсовая работа [1,1 M], добавлен 28.06.2013Метод Гаусса–Жордана: определение типа системы, запись общего решения и базиса. Выражение свободных переменных с использованием матричного исчисления. Нахождение координат вектора в базисе. Решение системы уравнений по правилу Крамера и обратной матрицей.
контрольная работа [200,4 K], добавлен 17.12.2010Метод Эйлера: сущность и основное содержание, принципы и направления практического применения, определение погрешности. Примеры решения задачи в Excel. Метод разложения решения в степенной ряд. Понятие и погрешность, решение с помощью метода Пикара.
контрольная работа [129,0 K], добавлен 13.03.2012Экзаменационные задачи по математике: расчет процентной концентрации раствора; решение уравнений и неравенств; задачи по геометрии, планиметрии и стереометрии; определение тригонометрических функций, вероятности события; нахождение экстремумов функции.
задача [493,9 K], добавлен 28.12.2011Выбор оптимального варианта распределения вертолетов по объектам удара и оценка его эффективности по математическому ожиданию поражаемой силы. Процесс математического моделирования прикладной задачи методом оптимизации аддитивной целевой функции.
курсовая работа [59,4 K], добавлен 18.12.2009Двойственные задачи в линейном программировании. Симметричные и несимметричные двойственные задачи. Связь исходной и двойственной задач. Анализ моделируемой ситуации (моделируемого объекта). Реализация двойственности на Visual Basic for Application.
курсовая работа [703,5 K], добавлен 14.10.2011Пример решения задачи на нахождение корня уравнения. Определение веса бетонного шара. Коэффициент полезного действия: понятие, формула. Нахождение значения функции. Плоскость основания цилиндра. Угол между плоскостью сечения и основания цилиндра.
контрольная работа [57,2 K], добавлен 27.12.2013Решение первой задачи, уравнения Пуассона, функция Грина. Краевые задачи для уравнения Лапласа. Постановка краевых задач. Функции Грина для задачи Дирихле: трехмерный и двумерный случай. Решение задачи Неймана с помощью функции Грина, реализация на ЭВМ.
курсовая работа [132,2 K], добавлен 25.11.2011Нахождение экстремумов функций методом множителей Лагранжа. Выражение расширенной целевой функции. Схема алгоритма численного решения задачи методом штрафных функций в сочетании с методом безусловной минимизации. Построение линий ограничений.
курсовая работа [259,9 K], добавлен 04.05.2011
