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

17

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

Исследование операций

Задание 1

математический линейный программирование

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

Стоимость 1 тонны породы №1 - 5 т.р., породы №2 - 2 т.р. Первый тип породы содержит меди, железа и цинка соответственно 5, 2.5, 1 единиц на тонну, а второй тип породы - соответственно 3, 3, 1.3 единиц.

Сколько породы каждого типа в день нужно обрабатывать, чтобы затраты на сырье были минимальны, если план производства предусматривает получение меди не менее 250 единиц в сутки, железа - не менее 150, а цинка - не менее 100 единиц.

Сведем данные в таблицу

Математическая модель задачи

- Выражение для целевой функции

Обозначим через x1, x2 количество породы соответственно I и II типа.

Целевая функция:

z=5000x1+2000x2 min

Система ограничений задачи

x10, x20

- Приведем к виду основной задачи линейного программирования:

z1=-z=-5000x1-2000x2max

z1=-z=-5000x1-2000x2+0x3+0x4+0x5max

Геометрическая трактовка модели задачи и ее решения

- Определение области допустимых значений

- Определим на графике точку, доставляющую экстремальное значение целевой функции.

Точка пересечения прямой 1 оси x2.

(0; 83.333)

Откуда экстремальное значение целевой функции: F=166666.67.

Ответ

Для минимизации затрат на сырье можно ограничиться сырьем второго типа в количестве 83.33 ед./день, при этом затраты на сырье составят 166666.67 р.

Задание 2

- Исходные данные

- Условия в развернутой форме

Q=25x1-x2+3x3-x4 > min

- Определим, существуют ли допустимые решения, для этого необходимо проверить совместность системы, т.е. найти ранги матрицы и расширенной матрицы

r(A)=r(R)=3,

следовательно, система совместна.

- Приведем условия задачи к каноническому виду. Выберем в качестве базисных переменных x1, x3 и x5.

Подставив выражения для x3 и x5 в первое уравнение системы, получим x1=16-(7x2+8x4). Т.о., имеем:

Целевая функция:

Q=25x1-x2+3x3-x4 > min

Q1=-Q=-25x1+x2-3x3+x4 > max

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

Q1=-379-(-167x2-211x4)

- Для решения построим симплексную таблицу

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

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

Перепишем таблицу, заменив переменные. Элементы разрешающего столбца и строки заменим числами, стоящими в нижних частях этих ячеек. Каждый из оставшихся элементов - суммой чисел, стоящих в верхней и нижней части этой ячейки. Т.к. величина элементов столбца свободных членов уменьшилась по абсолютной величине, есть основания надеяться, что замена элементов правомерна. Повторим вышеизложенные операции (выбор разрешающего элемента, вычисление новых значений) для новой таблицы.

Еще раз пересчитаем таблицу.

Т.к. ни столбец свободных, ни строка целевой функции не имеют ни одного отрицательного элемента, то оптимальное решение найдено.

X=(0; ; ; ; 0)

Значение целевой функции Q=-

Проверим найденные значения, подставив их в первоначальную систему:

Условия задачи в матричной форме

Поставки A=[600080003000]

Потребности B=[5000 2000 10000 6000 3000]

Тарифы C=

?Ai=17000, ?Bi=26000, следовательно, необходимо ввести фиктивного поставщика Aф с запасом 26000-17000=9000 ед.

Определим опорный план задачи методом минимального элемента

Т.к. число заполненных клеток должно быть 4+5-1=8, то введем две нулевые перевозки

Найдем значение функции при данном опорном плане:

F=

Определим оптимальный план задачи

Проверим оптимальность плана. Воспользуемся методом потенциалов. Для каждой заполненной клетки выполняется соотношение ui+vj=cij. Примем u1=0, остальные потенциалы вычисляются через базисные клетки.

Далее для свободных клеток найдем т.н. псевдотарифы ij следующим образом: ij= ui+vj.

Таблица

Найдем клетки, для которых разность cij-ij отрицательна.

Пересечение строки A1 и столбца B4 cij-ij=0.07-0.095=-0.025

Пересечение строки A3 и столбца B4 cij-ij=0.09-0.125=-0.035

Пересечение строки Aф и столбца B4 cij-ij=0 - 0.09 = -0.09

Построим цикл пересчета для клетки, находящейся на пересечении строки Aф и столбца B4.

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

Новая симплекс-таблица:

Найдем значение функции: F=930, общая стоимость перевозок не изменилась, т.к. поставка, перевозимая по циклу, равна нулю.

Проверим оптимальность плана

В таблице нет свободных клеток с отрицательной разностью cij-ij, значит, оптимальный план найден. Для клетки, находящейся на пересечении строки Aф и столбца B2 cij-ij=0, это означает, что существует еще один или несколько оптимальных планов с такой же общей стоимостью перевозок F=930.

Задание 4

A=

B=[5 1]

c11=1, c12=-2, c22=2

P=[15 10]

Т.о., целевая функция

F = c11x12+c22x22+c12x1x2+b1x1+b2x2 =x12 + 2x22 - 2x1x2 + 5x1 + x2 (min)

F1=-F= -x12 - 2x22 + 2x1x2 - 5x1 - x2 (max)

Условия

т.е.,

, или

- Определим стационарную точку целевой функции

Найдем частные производные целевой функции и приравняем их к нулю

По x1: -2x1+2x2-5=0

По x2: 2x1 -4x2-1=0

Откуда получаем стационарную точку (-5.5; -3).

- Исследуем функцию на вогнутость в окрестностях стационарной точки

Найдем вторые частные производные

Проверим на вогнутость:

=> функция вогнута.

- Составим функцию Лагранжа

L (x1,x2,u1,u2)= -x12 - 2x22 + 2x1x2 - 5x1 - x2+ u1(15-2x1-3x2)+ u2(10-x1-2x2)

Найдем частные производные для функции Лагранжа

Приведем полученные неравенства к следующему виду:

Преобразуем неравенства в равенства:

- Используя метод искусственных переменных, составим симплекс-таблицу

Составим псевдоцелевую функцию: ц=My1+My2 min

Выберем в качестве базисных переменные y1,y2,щ1, щ2.

Тогда система примет вид:

Псевдоцелевая функция: ц'=-My1-My2 max

Подставив выражения для y1 и y2 из системы, получим ц'=-6M-(4Mx1-6Mx2+5Mu1+3Mu2-Mv1-Mv2).

Занесем полученные значения в симплекс-таблицу.

Следующий шаг

Т.к. на следующем шаге на пересечении строки ц' и столбца свободных членов образуется нуль, поэтому пересчитаем лишь столбец b и строку ц'.

Т.о., x1=0, x2=

Проверим, выполняются ли условия дополняющей нежесткости:

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

Т.к. условия дополняющей нежесткости выполняются, то решение найдено.

Итак, x1=0, x2=;

F = x12 + 2x22 - 2x1x2 + 5x1 + x2 =

Размещено на Allbest.ru