Задачи на тему Решение задач «Исследование операций и методы оптимизации»

Содержание:

Лабораторная работа 1. Задачи безусловной оптимизации. 3

Лабораторная работа 2. Метод множителей Лагранжа решения задач условной оптимизации. 7

Лабораторная работа 4. Решение задачи о ранце методом ветвей и границ. 12

Лабораторная работа 5. Решение задачи коммивояжера методом ветвей и границ. 15

Лабораторная работа 6. Решение задачи целочисленного линейного программирования методом ветвей и границ. 26

Лабораторная работа 7. Решение задачи о назначениях. 54

Список использованных источников 61

Фрагмент текста работы:

Лабораторная работа 1. Задачи безусловной оптимизации.

Задание

По содержательной постановке построить математическую модель задачи. Нелинейная целевая функция должна содержать не менее 3-х управляемых параметров. Сформулировать необходимые и достаточные условия локального экстремума. Найти все стационарные точки функции. Анализируя матрицу Гессе в этих точках, найти среди них точки локального минимума и локального максимума.

Ход выполнения работы

Теория

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

1. Постановка задачи

Небольшой швейный цех шьет три модели рабочей формы. Обозначим их как х1, х2, х3. Продукция отпускается оптовым покупателям прямо из магазина при цехе по следующим ценам (4 — х1), (2 — 3 х2) и (5 + 2 х1 — 2х3). Найти оптимальное соотношение по количеству выпускаемой продукции для получения максимальной прибыли.

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

x ̅= (х1,х2,х3)→х1: (4 — х1)+x2: (2 — 3 х2)+x3: (5 + 2 х1 — 2х3)

F(x ̅)= х1 (4 – х1)+x2 (2 – 3 х2)+x3 (5 + 2 х1 – 2х3)→max

F(x ̅)=4×1-x_1^2 + 2×2-〖3x〗_2^2+5×3+2x1x3-〖2x〗_3^2→extr

3. Поиск оптимального плана

Найдем стационарные точки. Проверим достаточное условие экстремума.

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

2. Решая систему, получим стационарную точку:

X0 = (6.5; 0.333; 4.5)

Составим матрицу Гессе

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

Составим матрицу Гессе.

G(X)= -2 0 2

0 -6 0

2 0 -4

Вычисляем значения для точки X0(6.5; 0.333; 4.5)