Xreferat.com » Рефераты по экономико-математическому моделированию » Экономико-математический практикум

Экономико-математический практикум

РОССИЙСКАЯ ФЕДЕРАЦИЯ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ИНСТИТУТ ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ

СПЕЦИАЛЬНОСТЬ «Менеджмент организаций »


К О Н Т Р О Л Ь Н А Я Р А Б О Т А

По предмету: Экономико-математический практикум


Выполнил:

Студент 2 курса

4 семестр

Рахимова Лидия Рустамовна


Ташкент,2009

Задача № 1


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

Необходимо выполнить в указанном порядке следующие задания.

1. Найти оптимальный план прямой задачи:

а) графическим методом;

б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).

2. Построить двойственную задачу.

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

4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».

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

6. Найти оптимальное целочисленное решение:

а) графическим методом;

б) Методом Гомори.

Сравнить значения функций целочисленного и нецелочисленного решений

4Экономико-математический практикум

Решение задачи 1

1. Найдем оптимальный план решения графическим методом:


Экономико-математический практикум;

Экономико-математический практикум


Построим на координатной плоскости Ох1х2 граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе):


Экономико-математический практикум Экономико-математический практикум Экономико-математический практикум


Область допустимых решений определяется многоугольником ОАВСD (см. график 1).

Для линий уровня х1 - 3х2 = h (h — const) строим нормальный вектор Экономико-математический практикум. Перпендикулярно нормальному вектору построим одну из линий уровня (на рис. 1 она проходит через начало координат) Так как задача на минимум, то перемещаем линию уровня в направлении вектора Экономико-математический практикум до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L3 и L4, т. е. через точку Экономико-математический практикум. Для определения координат точки P решаем систему уравнений

Экономико-математический практикум.


Получаем х1 = 5,3, х2 = 0,6. Это и будет оптимальным решением данной задачи, которому соответствует минимальное значение целевой функции Zmin=3,5


Экономико-математический практикум


Экономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Экономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум Экономико-математический практикум


Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум


Экономико-математический практикум


Экономико-математический практикум

Экономико-математический практикум


График № 1

1б) Перейдем к расширенной задаче:


Экономико-математический практикум


Данная расширенная задача имеет начальное опорное решение Экономико-математический практикум с базисом Экономико-математический практикум. Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:


Экономико-математический практикум


Расчеты проведем в таблице (Табл. 1)


Таблица 1





1 -3 0 0 0 0 M

Б

Сб В А1 А2 А3 А4 А5 А6 А7

А3 0 9 -2 3 1 0 0 0 0

А4 0 53 5 2 0 1 0 0 0

А5 0 17 4 -7 0 0 1 0 0
← А7 М 37 6 8 0 0 0 1 1

Экономико-математический практикум

0 –1 3 0 0 0 0 0

Экономико-математический практикум

37 6 8 0 0 0 0 0

Начальное опорное решение не является оптимальным, так как в задаче на минимум имеются положительные оценки. Выбираем номер вектора Аk, вводимого в базис опорного решения, и вектора Аl, выводимого из базиса. Наибольшая положительная оценка соответствует А2, за разрешающий элемент выбираем коэффициент 8 и выполняем преобразование Жордана.

Вектор А2 выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем второе опорное решение Экономико-математический практикум с базисом Экономико-математический практикум (табл. 1.3). Целевая функция Экономико-математический практикум =-3М -21. Это решение не является оптимальным, так как есть положительная оценка.


Таблица 1

Б

Сб B А1 А2 А3 А4 А5 А6 
А2 -3 3,0 -0,7 1,0 0,3 0,0 0,0 0,0 0,0
А4 0 47,0 6,3 0,0 -0,7 1,0 0,0 0,0 0,0
А5 0 38,0 -0,7 0,0 2,3 0,0 1,0 0,0 0,0
a7 М 13,0 11,3 0,0 -2,7 0,0 0,0 1,0 1,0
M+1 -9,0 1,0 0,0 -1,0 0,0 0,0 0,0 0,0
M+2 13,0 11,3 0,0 -2,7 0,0 0,0 0,0 0,0
A2 -3 -2,4 -0,6 1,0 0,0 0,0 -0,1 0,0 0,0
a4 0 57,9 6,1 0,0 0,0 1,0 0,3 0,0 0,0
А3 0 16,3 -0,3 0,0 1,0 0,0 0,4 0,0 0,0
A7 М 56,4 10,6 0,0 0,0 0,0 1,1 1,0 1,0
M+1 7,3 0,7 0,0 0,0 0,0 0,4 0,0 0,0
M+2 56,4 10,6 0,0 0,0 0,0 1,1 0,0 0,0
A2 -3 0,6 0,0 1,0 0,0 0,0 -0,1 0,1 0,1
a4 0 25,1 0,0 0,0 0,0 1,0 -0,4 -0,6 -0,6
А5 0 17,8 0,0 0,0 1,0 0,0 0,5 0,0 0,0
A1 1 5,3 1,0 0,0 0,0 0,0 0,1 0,1 0,1


3,5 0,0 0,0 0,0 0,0 0,4 -0,1 -0,1


0,0 0,0 0,0 0,0 0,0 0,0 -1,0 -1,0

Целевая функция после второй итерации равна Экономико-математический практикум = 3,5. Все оценки отрицательные, план оптимален.


Экономико-математический практикум


Оптимальный план исходной задачи Х*=(х1*=5,3; х2*=0,6). Минимальное значение целевой функции исходной задачи =3,5.


Ответ: min Z(X*) =3,5.


2. Двойственная задача


Двойственная задача имеет вид.


Экономико-математический практикум


при условиях


Экономико-математический практикум


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


Экономико-математический практикум


Откуда следует:


Экономико-математический практикум


4. Оптимальный план двойственной задачи найдем, используя окончательную симплекс-таблицу прямой задачи (Табл.1)


Экономико-математический практикум


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

Проанализируем решение задачи, используя условия дополняющей нежесткости (вторую теорему двойственности). Подставляем координаты оптимального решения двойственной задачи Y* = (0;0;-0,35;-0,068), в систему ограничений.


Экономико-математический практикум


Ответ: Z(X) =3,5 при Х* = (0;0;-0,35;-0,068).


Задача № 2


Каноническая задача

В каждом варианте приведены таблицы, в которых записаны условия канонической задачи линейного программирования на минимум, т. е.


Экономико-математический практикум


В первой строке помещены коэффициенты целевой функции. В остальных строках, в первых пяти столбцах, находятся векторы условий, а в последнем столбце записан вектор ограничений. В правом верхнем углу таблицы указана цель задачи.

Необходимо последовательно выполнить следующие задания.

Задачу решить графическим методом.

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

Построить двойственную задачу. Если вектор Экономико-математический практикум найден, вычислить оптимальный план Экономико-математический практикум двойственной задачи, используя первую теорему двойственности Экономико-математический практикум. Вычислить максимальное значение функции Экономико-математический практикум.

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


Если Экономико-математический практикум, то Экономико-математический практикум.

Если Экономико-математический практикум, то Экономико-математический практикум.



14



1 -5 6 8 -2 min
11 7 1 12 5 16
14 10 0 3 8 17
13 2 9 4 6 15

Решение задачи 2

Представим исходные данные задачи в виде:

Экономико-математический практикум


Экономико-математический практикум


Проверяем, применим ли графический метод при решении данной задачи.


Экономико-математический практикум


линейно независимы, так как их координаты непропорциональны. Поэтому ранг системы векторов-условий r = 3. Находим n - r =5 - 3 = 2 Ј 2. Следовательно, метод применим.

Приведём систему уравнений-ограничений к равносильной, разрешённой методом Жордана–Гаусса. Преобразуем систему уравнений методом Жордана-Гаусса до получения общего решения (табл. 2.1).


Таблица 2.1.

№ итерац.

x1

x2

x3

x4

x5

bi


(1)

11 7 1 12 5 16

14 10 0 3 8 17

13 2 9 4 6 15

(2)

-45,00

-33,00

1,00

0,00

-27,00

-52,00


4,67

3,33

0,00

1,00

2,67

5,67


-5,67

-11,33

9,00

0,00

-4,67

-7,67


(3)

2,25

0,75

1,00

10,13

0,00

5,38


1,75

1,25

0,00

0,38

1,00

2,13


2,50

-5,50

9,00

1,75

0,00

2,25

(4)

-12,21

32,57

-51,07

0,00

0,00

-7,64


1,21

2,43

-1,93

0,00

1,00

1,64


1,43

-3,14

5,14

1,00

0,00

1,29

(5)

0,24

-0,64

1,00

0,00

0,00

0,15


1,68

1,20

0,00

0,00

1,00

1,93


0,20

0,14

0,00

1,00

0,00

0,52


Общее решение системы уравнений имеет вид


Экономико-математический практикум


Учитывая, что все переменные неотрицательны, перейдем от уравнений к неравенствам из общего решения системы.

Экономико-математический практикум


откуда получим систему неравенств с двумя переменными


Экономико-математический практикум


Целевую функцию выразим через свободные переменные


Экономико-математический практикум


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


Экономико-математический практикум


Строим область допустимых решений (график 2). Любая точка многоугольника Экономико-математический практикум удовлетворяет системе неравенств. Вершина Экономико-математический практикум является точкой входа семейства прямых Экономико-математический практикум в область решений, следовательно, в этой точке она принимает минимальное значение.

В свою очередь, Экономико-математический практикум=(1,32;0,12).

Решая систему уравнений получаем х1 =2,2, х2 =0,6. Это и будет оптимальным решением данной задачи, которому соответствует минимальное значение целевой функции Zmin


Экономико-математический практикум.

Экономико-математический практикум


Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Экономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Экономико-математический практикум A

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум А

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум


Экономико-математический практикум

(3)


график 2

2.Решим симплекс-методом задачу линейного программирования, используя метод искусственного базиса


Экономико-математический практикум

Экономико-математический практикум


Составим расширенную задачу. В левые части уравнений системы ограничений вводим неотрицательные искусственные переменные с коэффициентом +1. Удобно справа от уравнений записать вводимые искусственные переменные. В первое уравнение вводим переменную х6, во второе — переменную х7, в третье – х8. Данная задача — задача на нахождение минимума. Получаем


Экономико-математический практикум

Экономико-математический практикум


Данная расширенная задача имеет начальное опорное решение Экономико-математический практикум с базисом Экономико-математический практикум. Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:

Экономико-математический практикум


Записываем исходные и расчетные данные в симплексную таблицу (табл.2.2).


Таблица 2.2





1 -5 6 8 -2 М M M

Б

Сб А0 А1 А2 А3 А4 А5 А6 A7 A8

А6 М 16 11 7 1 12 5 1 0 0

A7 M 17 14 10 0 3
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: