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

 

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

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

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

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

 

СПЕЦИАЛЬНОСТЬ «БУХГАЛТЕРСКИЙ УЧЕТ, АНАЛИЗ И АУДИТ»

 

 

 

 

 

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

 

 

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

Вариант № 60

 

 

Выполнила:

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

5 семестр полная форма обучения

 

 

 

 

 

 

 

 

 

 

Задача 60

1. Необходимо, применяя метод полного исключения неизвестных (Жордана-Гаусса), найти любое общее и три базисных решения системы. Сделать проверку. Решение рекомендуется представить в виде таблицы.

 

 

Таблица. Решение:

 

Общее решение:

 

Xбаз1 = .

 

Проверка:

 

Таблица

 

xбаз2 = .

 

Проверка:

 

Таблица

 

xбаз3 = .

 

Проверка:

 

 

 

Задача 260

 

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

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

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

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

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

Если , то . Если , то .

 

Таблица

2	-1	8	15	24	min
4	2	9	12	13	64
3	8	5	11	10	56
2	6	8	7	7	38

 

Решение:

1. Рассмотрим каноническую задачу

 

 

 

Таблица

 

Получаем общее решение:

 

Т.к. , то

,

 

Строим граничные прямые

 

 

Рис.

 

Область решений 4-х угольник АВСД

Функция достигает минимума в точке А.

 

,

 

2. Решим задачу симплекс методом

 

 

Таблица

 

 

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

 

 

Проведем анализ полученного решения

 

 

Задача 460

 

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

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

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

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

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

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

 

 

Решение:

1. Решим задачу графическим методом

Строим граничные прямые

 

 

Рис.

 

Область решений – выпуклый 6-тиугольник ABCDEF

Функция достигает максимума в точке Д.

 

- оптимальный план прямой задачи

 

 

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

Для этого умножим 2-ое неравенство системы ограничений исходной задачи на (-1).

 

 

3. Условие дополняющей нежесткости

 

 

Граничные прямые (2) и (3) не проходят через оптимальную точку, следовательно,

 

 

Получим систему уравнений

 

- оптимальный план двойственной  задачи

=

 

Найдем оптимальный план прямой задачи симплекс-методом

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

 

 

Расширенная задача

 

 

Таблица

 

- оптимальный план прямой задачи,

4. Оптимальное решение двойственно  задачи определим из соотношения:

 

- оптимальный план двойственной  задачи

=

 

Т.е., целевые функции совпадают.

5. Решим двойственную задачу симплекс-методом

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

 

,

 

Расширенная задача:

 

,

 

Таблица

 

- оптимальный план двойственной  задачи

=

 

Найдем оптимальный план прямой задачи по I теореме двойственности:

 

- оптимальный план прямой задачи

 

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

 

Задача 560

 

Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.

 

Рис.

 

Решение:

1. Метод северо-западного узла

 

Рис

 

 

Рис.

 

 

Рис

 

 

Рис.

 

Рис.

 

 

 

Рис.

 

Рис.

 

 

Рис

 

 

Рис.

 

 

 

2. Метод минимального элемента

 

Рис

 

 

Рис

 

 

Рис.

 

 

 

Рис.

 

 

Рис.

 

 

Рис.

 

 

Рис.

 

Рис.

 

 

Задача 660

 

Задача изображена в виде неориентированного связного графа. На ребрах записаны значения удельных стоимостей , на вершинах (в кружках) – значения запасов-потребностей . Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.

 

 

Рис.

 

Решение:

Процесс решения задачи начинается с построения опорного плана и проверки оптимальности методом потенциалов

 

Рис.

 

Число вершин = 13, число ребер=20, число базисных ребер=13-1=12.

 

 

Рис.

 

Рис.

 

 

Задача 560

 

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

 

Таблица

51	47	10	30	44	22	38
29	21	22	27	10	43	3
6	42	35	39	34	45	26
25	14	18	21	23	47	15
4	36	21	36	31	13	41
40	11	33	7	35	37	19
9	20	50	45	46	48	53

 

Решение:

 

 

Таблица. Венгерский метод

51	47	10	30	44	22	38
29	21	22	27	10	43	3
6	42	35	39	34	45	26
25	14	18	21	23	47	15
4	36	21	36	31	13	41
40	11	33	7	35	37	19
9	20	50	45	46	48	53