Вопросы к курсу «Исследование операций»

Вопросы к курсу «Исследование операций»

1.  Предмет и цели исследования операций. Общие понятия

2.  Общая характеристика и по­следовательность решения задач в исследованиях операций. Основные отличия метода исследования операций

3.  Основные задачи, решаемые методом исследования операций. Классификация задач.

4.  Методы отыскания оптимальных решений в задачах исследования операций. Классификация методов.

5.  Экономико-математическое моделирование в теории исследования операций.

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

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

8.  Постановка и модель задачи определения оптимального использования мощностей оборудования.

9.  Понятие задачи линейного программирования. Примеры.

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

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

12.  Симплекс-метод. Геометрическая интерпретация симплексного метода.

13.  Взаимно двойственные задачи линейного программирования и их свойства.

14.  Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов

15.  Теоремы двойственности

16.  Целочисленные задачи линейного программирования. Методы решения. Задача коммивояжера.

17.  Постановка и экономико-математическая модель транспортной задачи.

18.  Экономические задачи, сводящиеся к транспортным.

19.  Методы составления первоначальных опорных планов в транспортной задаче. Пример

20.  Системы управления запасами. Общие понятия. Модель оптимального размера заказа.

21.  Назначение и области применения сетевого планирования и управления (СПУ). Сетевая модель и ее основные элементы. Порядок и правила построения сетевых графиков. Понятие о критическом пути.

22.  Линейная диаграмма проекта. Временные параметры сетевых графиков.

Задачи для экзамена по курсу «Исследование операций» ИДО УлГТУ

1. Построить экономико-математическую модель следующей задачи распределения ресурсов: Предприятие изготавливает два вида продукции - П1 и П2, используюя два вида сырья - А и В. Суточные запасы сырья и его расход на единицу продукции вида П1 и вида П2 дан в табл.

Известно, что суточный спрос на продукцию П2 никогда не превышает 3 ед. в сутки. Оптовые цены единицы продукции равны: 3 д. е. - для П1 и 4 д. е. для П2.

Необходимо определить такие объемы суточного производства продукции П1 и продукции П2, при которых совокупный доход будет максимальным.

Решение:

а) Идентификация переменных задачи: модель строится для нахождения объемов суточного производства продукции П1 и продукции П2. Обозначим эти величины x1 и x2. Ясно, что x1 ≥ 0и x2 ≥ 0.

б) Смоделируем ограничения должны быть наложены на переменные:

Опишем строку матрицы, соответствующую сырью А.

Для производства продукции П1 в количестве x1 и продукции П2 в количестве x2 и потребуется сырье А в количестве 2x1 + 3x2, а запас сырья равен 9 единицам, следовательно должно выполняться неравенство

2x1 + 3x2 ≤ 9, (1)

соответствующее ограниченности сырья А.

Аналогично построим условие, соответствующее ограниченности сырья Б.

1·x1 + 2x2 ≤

в) смоделируем цель задачи:

Производств продукции П1 и П2 в в количестве x1 и x2 принесет доход в сумме 2x1 + 3x2. Цель производителя – получить максимальный доход. Следовательно, целевая функция задачи имеет вид

f(x) = 2x1 + 3x2 = max. (3)

Ответ:

Переменные задачи:

Целевая функция задачи: x1, x2 (причем естественно

f(x) = 2x1 + 3x2 = max.

Ограничения задачи:

2x1 + 3x2 ≤ 9,

1·x1 + 2x2 ≤ 10,

x1 ≥ 0,

x2 ≥ 0.

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

min f(x) = 6x1 + 4x2 ;

3x1 - x2 ≤ 2;

x1 + 2x2 ≥ 1;

x1 ≥ 0; x2 ≥ 0.

Решение:

а) Преобразование целевой функции:

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

б) Преобразование ограничений:

Правые части неравенств уже положительны. Чтобы неравенства превратить в равенства к левой части первого неравенства добавим новую неотрицательную переменную x3, а от левой части второго неравенства отнимем новую неотрицательную переменную x4. В результате получим два ограничения в виде равенств

3x1 - x2 + x3 = 2;

x1 + 2x2 - x4 = 1.

в) переменные x1, x2 неотрицательны по условию.

Ответ: Каноническая форма

min f(x) = 6x1 + 4x2 ;

3x1 - x2 + x3 = 2;

x1 + 2x2 - x4 = 1.

x1 ≥ 0; x2 ≥ 0.

3. Показать на координатной плоскости:

3.1. Полуплоскость, удовлетворяющую уравнению

x1 - 3x2 ≤

Решение:

а) Построим прямую

L: x1 - 3x2 =

Для этого найдем две точки А и В, принадлежащие прямой L.

т. А: положим x1 = 0, тогда из соотношения (5) получим

-3x2 = 2, т. е. x2 = -2/3 = -0,667.

Таким образом т. А имеет координаты (0, -0,667).

т. В: : положим x2 = 0, тогда из соотношения (5) получим

x1 = 2.

Таким образом т. В имеет координаты (2, 0).

б) Проверим – принадлежит ли начало координат (0, 0) искомой области. Подставим координаты x1 = 0, x2 = 0 в неравенство (4) и получим

0 ≤ 2,

т. е. неравенство выполняется и начало координат принадлежит искомой области (рис).

Ответ: Искомая область лежит выше прямой L.

3.2. Допустимую область удовлетворяющую системе ограничений:

x1 + 2x2 ≤ 4.

x1 ≥ 0; x2 ≥ 0.

Решение:

а) Построим прямую

L: x1 + 2x2 =

Для этого найдем две точки А и В, принадлежащие прямой L.

т. А: положим x1 = 0, тогда из соотношения (6) получим

2x2 = 4, т. е. x2 = 2.

Таким образом т. А имеет координаты (0, 2).

т. В: : положим x2 = 0, тогда из соотношения (6) получим

x1 = 4.

Таким образом т. В имеет координаты (4, 0).

б) Проверим – принадлежит ли начало координат (0, 0) искомой области. Подставим координаты x1 = 0, x2 = 0 в неравенство x1 + 2x2 ≤ 4 и получим

0 ≤ 4,

т. е. неравенство выполняется и начало координат принадлежит искомой области, задаваемой первым неравенством (рис).

б) Условие x1 ≥ 0 говорит о том, что искомая область лежит правее вертикальной оси координат (прямая L2).

Условие x2 ≥ 0 говорит о том, что искомая область лежит выше горизонтальной оси координат (прямая L3).

Результатом пересечения трех областей, определяемых прямыми L1, L2, L3 является треугольник ОАВ.

Ответ: Искомая область есть треугольник ОАВ.

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

Целевая функция F = 3 х1 + 4х2 = max.

Ограничения:

Решение

Построим многоугольник решений (рис.2.5). Для этого в системе координат X10X2 на плоскости изобразим граничные прямые:

2х1 + 3х2 = 9 (L1);

3х1 + 2х2 = 13 (L2);

х1 - х2 = 1 (L3);

х2 = 2 (L4).

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

Для построения прямой Z = 3х1 + 4х2 = 0 строим вектор-градиент и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора . Из рис. следует, что по отношению к многоугольнику решений опорной эта прямая остановится в точке C, где функция принимает максимальное значение. Точка С лежит на пересечении прямых L1 и L3. Для определения ее координат решим систему уравнений:

Оптимальный план задачи х1=2,4; х2=1,4. Подставляя значения х1 и х2 в линейную функцию, получим:

.

Полученное решение означает, что объем производства продукции П1 должен быть равен 2,4 ед., а продукции П2 – 1,4 ед. Доход, получаемый в этом случае, составит: Z = 12,8 д. е.

Рис. 2.5. Решение задачи линейного программирования геометрическим способом

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

:

при ограничениях: