Размещено на http://www.allbest.ru/

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

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

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

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

По дисциплине:

"Методы оптимальных решений"

Выполнил: Тарасова Т.В. Группа: ФКТ-32

Новосибирск, 2015

Задача 1

Решить графически задачу из лабораторной работы №1.

Решение

Введем переменные: x₁ - количество кабеля типа I, x₂ - количество кабеля типа II. По определению эти переменные должны быть неотрицательны. При связи, использующей x₁ кабелей I типа и x₂ кабелей II типа, могут использоваться 5x₁+x₂ телефонных каналов, 5x₁+4x₂ телеграфных каналов и 2x₁+5x₂ фототелеграфных каналов. Для осуществления связи необходимо наличие не менее требуемого количества каналов. Получаем ограничения на количества имеющихся каналов:

Затраты на осуществление связи, имеющей x₁ кабелей I типа и x₂ кабелей II типа, составят: (11x₁+x₂)1000=11000x₁+1000x₂ условных единиц. Получаем математическую модель задачи:

5x₁+x₂?12

5x₁+4x₂?33

2x₁+5x₂?20

x₁; x₂?0, целое.

P(x)=11000x1+1000x2?min

5x₁+x₂?12 x₂?12-5x₁

5x₁+4x₂?33 x₂?33/4-5x₁/4

2x₁+5x₂?20 x₂?4-2x₁/5

x₁; x₂?0, целое. x₁; x₂?0, целое.

Первое неравенство системы ограничений задачи x₂?12-5x₁ описывает полуплоскость, лежащую выше прямой x₂=12-5 x₁, которую строим по точкам (1;7) и (2;2).

Второе неравенство системы ограничений задачи x₂?33/4-5x₁/4 описывает полуплоскость, лежащую выше прямой x₂=33/4-5x₁/4, которую строим по точкам (1;28/4) и (2;23/4).

Третье неравенство системы ограничений задачи x₂?4-2x₁/5 описывает полуплоскость, лежащую выше прямой x₂=4-2x₁/5, которую строим по точкам (1;18/5) и (2;16/5).

Неограниченная сверху область ABC - множество допустимых решений системы ограничений задачи.

Строим линию уровня , т.е. 11000x₁+1000x₂=0 x₂=-11x₁

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора - точка (0; 0), конец - точка (11000; 1000). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области.

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых 5x₁+x₂=12 и x₁=0, найдем ее координаты, решив систему уравнений:

5x₁+x₂=12

x₁=0

Решив систему уравнений, получим: x₁ = 0, x₂ = 12

Откуда найдем минимальное значение целевой функции:

F(X) = 11000*0 + 1000*12 = 12000

Задача 2

Составить двойственную задачу к задаче 1. Найти ее решение по теореме равновесия.

Решение. Составим двойственную задачу к данной

5x₁+x₂?12

5x₁+4x₂?33

2x₁+5x₂?20

x₁; x₂?0, целое.

5y₁+5y₂+2y3?11000

y₁+4y₂+5y₃?1000

y₁; y₂; y₃?0

F=12y₁+33y₂+20y₃>max

Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости

y₁(5x₁+x₂-12)=0

y₂(5x₁+4x₂-33)=0

y₃(2x₁+5x₂-20)=0

x₁(5y₁+5y₂+2y₃-11000)=0

x₂(y₁+4y₂+5y₃-1000)=0

Подставим в составленную систему оптимальное решение исходной задачи X_опт=(0;12):

y₁(5*0+12-12)=0

y₂(5*0+4*12-33)=0

y₃(2*0+5*12-20)=0

x₁(5y₁+5y₂+2y₃-11000)=0

x₂(y₁+4y₂+5y₃-1000)=0

y₁(0+0)=0

y₂(0+33-33)=0

y₃(0+60-20)=0

x₁(5y₁+5y₂+2y₃-11000)=0

x₂(y₁+4y₂+5y₃-1000)=0

y₁*0=0;

y₂*0=0

y₃*40=0; y₃=0

x₁(5y₁+5y₂+2y₃-11000)=0

x₂(y₁+4y₂+5y₃-1000)=0

Тогда



x₁(5y₁+5y₂+2*0-11000)=0

x₂(y₁+4y₂+5*0-1000)=0

0(5y₁₊5y₂-11000)=0

12(y₁₊4y₂-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=12y₁+33y₂+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