Исследование операций и принятие решения
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
).
L = 5*x1+x2-x3+x4 +2x5 max
Решение
Приведем данное нам условие к стандартной форме записи и получим следующее
L = 0 (-5*x1-x2+x3-x4 -2x5 ) max
Видим, что x1,x2-свободные переменные и x3,x4,x5 базисные; n= 5, m=3, k= 2.
Заполним стандартную таблицу
bL=2
Поясним действия, проделанные выше за пределами таблицы. Выбрав в качестве разрешающего столбца x2. Далее в этом столбце нужно выбрать разрешающий элемент. Для этого рассмотрим все элементы данного столбца, имеющие одинаковый знак со своим свободным членом. Из них в качестве разрешающего выберем тот, для которого отношение к нему свободного члена будет минимально. Отсюда понятно, почему в качестве разрешающей строки мы выбрали x4.
bL
bL
bL
bL84.5120.512/31/6-1/34/35/61/3
Полученное решение удовлетворяет системе ограничений!
Ответ
L* = 8
x*4,x*5=0 свободные
- базисные
ЗАДАНИЕ N3
Условие
Решение транспортной задачи, все данные приведены ниже в таблице.
B1B2B3B4B5aiA10.090.120.140.10.093000A20.080.10.150.050.076000A30.10.150.150.080.068000bj10008000300030004000
Решение
Перед тем как приступить к решению, подсчитаем общее количество запасов и общее количество заявок . Понятно что имеем транспортную задачу с избытком заявок . Потребуем, чтобы все пункты назначения были удовлетворены в равной доле. При таком подходе задача сводится к задаче с правильным балансом: необходимо исправить поданные заявки, умножив каждую на коэффициент
k = ai bj . Рассчитаем k.
Тогда получим транспортную задачу с правильным балансом.
B1B2B3B4B5aiA10.090.120.140.10.093000A20.080.10.150.050.076000A30.10.150.150.080.068000bj17000
Найдем опорное решение с помощью метода северо-западного угла.
r = 3+5-1 =7
B1B2B3B4B5aiA10.140.10.093000A20.080.050.076000A30.10.158000bj17000
Проверим сумму по столбцам, сумму по строкам и количество базисных (заполненных) клеток.
Проверка по столбцам:
Проверка по строкам:
Количество заполненных клеток равно r =7. Найденный план является опорным.
Постараемся улучшить план перевозок
B1B2B3B4B5aiA10.140.10.093000A20.080.050.076000A30.10.158000bj17000
Подсчитаем цены выделенных пунктирными прямоугольниками циклов.
Цикл1
(1;1)-(1;2)-(2;2)-(2;1)
, где цена цикла
Цикл2
(2;3)-(2;4)-(3;4)-(3;3)
Для того чтобы стоимость плана уменьшилась, имеет смысл совершать перевозки только по тем циклам, цена которых отрицательна. Цена Цикла2 отрицательна, поэтому выбираем его. Цикл1 в данном случае рассматривать не будем: так как цена его положительна, поэтому план перевозок с помощью перерасчета этого цикла не улучшится.
После всех рассуждений получим следующее:
B1B2B3B4B5aiA10.140.10.093000A20.080.050.076000A30.10.158000bj17000
Итак, улучшаем план перевозок с помощью Цикла1. Для этого перенесем по циклу мнимальное количество груза, стоящее в отрицательной вершине.
B1B2B3B4B5aiA10.140.10.093000A20.080.076000A30.10.158000bj17000
Подсчитаем L для таблицы с изменениями.
L =
Допустим, что найдено оптимальное решение. Проверим его с помощью метода потенциалов.
Примем a1 = 0, тогда bj = cij ai (для заполненных клеток). Если найденное решение справедливо, то во всех пустых клетках таблицы ?ij = cij (ai + bj )?0. Ясно, что ?ij = 0 для заполненных клеток. Получим следующее.
b1=0.09b2=0.12b3=0.14b4=0.07b5=0.05aia1=03000a2=-0.026000a3=0.018000bj17000
Из таблицы видно, что найденное оптимальное решение верно, так как ?ij ?0.
Ответ
B1B2B3B4B5aiA10.140.10.093000A20.080.076000A30.10.158000bj17000
ЗАДАНИЕ N4
Условие
№b1b2c11c12c22extra11a12a21a22p1p2Знаки огр.
1 2
- 27123max24321020
Определить экстремум целевой функции вида
= 1112+2222+1212+11+22
при условиях
111+1221
211+2222 .
Решение
?(x1,x2)=
- Нужно определить относительный максимум функции для этого нужно определить стационарную точку
.
стационарная точка (-0,25;1.25)
- Исследовать найденную стационарную точку на максимум для чего определить вогнутость функции f.
-2<0
Условия выполняются, следовательно, целевая функция является строго вогнутой в окрестности стационарной точки.
- Составление функции Лагранжа.
AБ
Перепишем систему А.
А1
- Вводим дополнительные переменные v1,v2,w1,w2 ,превращающие неравенства системы А1 в равенства.
A2
перепишем систему Б
Б2 - условия дополняющей нежесткости
- Решить систему А2 с помощью метода искусственных переменных.
в 1 и 2-ое уравнение системы А2.
Вводим псевдоцелевую функцию
базисные переменные: y1,y2,w1,w2
свободные переменные:x1,x2,v1,v2,u1,u2
80MM4M0M4M01001.5000.5013.50-1.5-20.50.5-0.55008002058.5-15.541.5-0.51.5
Оптимальное решение:
y1=x1=u1=y2=w1=v2=0
x2=10
w1=50оптимальное решение
u2=13.5
v1=58.5
- проверим условие дополняющей нежесткости
xi*vi=0
ui*wi=0условия выполняются
x1=0
x2=10- решение исходной задачи квадратичного программирования
Ответ
x1=0
x2=10
Литература
Курс лекций Плотникова Н.В.