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

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

Федеральное государственное бюджетное

образовательное учреждение

высшего профессионального образования

«Самарский государственный аэрокосмический университет имени академика С.П.Королева

(национальный исследовательский университет)»

РЕШЕНИЕ ЗАДАЧ ИССЛЕДОВАНИЯ

ОПЕРАЦИЙ

Часть 1

Методические указания к лабораторным работам

Самара 2011 г.

УДК 519.8

Составитель: А.С.Кучеров

Решение задач исследования операций. Часть 1: Методические указания/ Самар. гос. аэрокосм. ун-т; Сост. А.С.Кучеров; Самара, 2011. 45 с

В методических указаниях приводятся типовые алгоритмы решения ряда задач исследования операций с использованием программного пакета Mathcad и табличного процессора Excell. Указания предназначены для студентов специальности 230301 «Моделирование и исследование операций в организационно-технических системах», изучающих учебную дисциплину «Исследование операций».

Подготовлены кафедрой летательных аппаратов.

Табл. 5. Ил. 10. Библиогр. 4 назв.

Печатаются по решению редакционно-издательского совета Самарского государственного аэрокосмического университета.

Рецензент – к.т.н., доцент Есипов Б.А.

Оглавление

ВВЕДЕНИЕ……………………………………………………..4

1 Задача Линейного программирования

1.1 Решение задачи с помощью пакета Mathcad………….5

1.1.1 Геометрический метод решения…………………...5

1.1.2 Решение задачи линейного программирования как

задачи оптимизации………………………………………7

1.2 Решение задачи с помощью процессора Excel………..8

1.3 Варианты заданий……………………………………...10

2 ТРАНСПОРТНАЯ ЗАДАЧА………………………………...14

2.1 Транспортная задача с оптимизацией плана

перевозок по критерию времени…………………………..14

2.2 Транспортная задача с оптимизацией плана

перевозок по критерию стоимости………………………..16

2.2.1 Решение задачи методом потенциалов…………...16

2.2.2Решение транспортной задачи как задачи

оптимизации………………………………………………21

2.3 Варианты заданий………………………………………22

3 ПОТОКИ В ОРГРАФАХ……………………………………25

3.1 Алгоритм нахождения максимального потока………..25

3.2 Варианты заданий……………………………………….29

4 ЗАДАЧА ДЖОНСОНА……………………………………….32

4.1 Алгоритм решения………………………………………32

4.2 Варианты заданий……………………………………….35

5 ЗАДАЧА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ...37

5.1 Алгоритм решения………………………………………37

5.2 Варианты заданий……………………………………….42

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ……………44

Введение

При изучении дисциплины «Исследование операций» большое значение имеет овладение методами решения практических задач. Многообразие задач исследования операций обусловило наличие широкого ассортимента учебно-методической литературы, что затрудняет студентам поиск необходимых пособий.

Настоящие методические указания ориентированы на те задачи, которые рассматриваются при чтении цикла лекций для студентов специальности 230301 «Моделирование и исследование операций в организационно-технических системах». Рассмотрены типовые задачи принятия решений в условиях определенности (детерминированные задачи исследования операций).

Для задач, решение которых связано с большим объемом расчетов, приводятся алгоритмы вычислений с помощью программного пакета Mathcad и табличного процессора Excel.

1 Задача Линейного программирования

1.1 Решение задачи с помощью пакета Mathcad

1.1.1 Геометрический метод решения

Рассмотрим следующий пример:

(1.1)

Для построения графиков ограничений заменим первые три неравенства равенствами и разрешим их относительно x₂:

(1.2)

График целевой функции вначале будем строить для ее значения, равного 0, т.е. по уравнению

(1.3)

Запустив программный пакет Mathcad, необходимо выполнить команду Insert/Graph►X-Y Plot. В черном прямоугольнике под осью абсцисс указать имя независимой переменной (здесь удобно использовать x, без индекса). В прямоугольник слева от оси ординат, через запятую, ввести правые части выражений (1.2), (1.3), а также 0 (для построения ограничения ).

Далее следует настроить масштаб по осям координат и увеличить график для удобства работы с ним.

Для настройки атрибутов линий необходимо дважды щелкнуть на поле графика, чтобы открыть диалоговое окно Formatting Currently Selected X-Y Plot (Форматировать выбранный график). На закладке Traces (Графики), выбрав в поле Legend Label (Метка легенды) график с нужным номером, можно с помощью полей выбора настроить следующие его атрибуты:

- тип маркера, помещаемого на линию (Symbol);

- тип линии (Line);

- цвет линии (Color);

- тип линии, изображенной под легендой графика (Type);

- толщину линии (Weight).

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

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

(1.4)

Для получения точного решения системы используется функция lsolve:

(1.5)

В выражении (1.5) A- это матрица коэффициентов системы уравнений, B – вектор значений правой части.

Рисунок 1.1 – Решение задачи линейного программирования