Федеральное агентство по образованию ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ" (ОмГТУ) Кафедра «Автоматизированные системы обработки информации и управления»
РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА по дисциплине «Теория принятия решений»
	Принял: преподаватель А.В. Зыкина подпись, дата Выполнил: студент гр. АС-314 В.В. Львов подпись, дата
Омск 2007

Содержание

Содержание 2

Введение 3

Задание 4

1 Построение математической модели 5

2 Теоретическая часть 6

2.1Симплекс метод 6

2.1.1Алгоритм симплекс-метода для задачи на минимум 6

2.1.2Алгоритм симплекс-метода для задачи на максимум 7

3 Практическая часть 8

Заключение 10

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

Введение

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

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

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

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

Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Можно сказать, что оно применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: задач управления запасами, задач планирования и управления, задач распределения ресурсов, оптимального размещения оборудования и др.

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

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

Задание

Задача о выборе производственной программы.

Имеются m предприятий на которых нужно произвести n продуктов в заданном ассортименте L₁, L₂, … , L_n. Известна производительность a_ij i-го предприятия в единицу времени, если она изготовляет j-й продукт. Предполагается, что max a_ij>0, то есть каждый продукт может производиться хотя бы на одном предприятии.

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

1 Построение математической модели

По заданию составляем целевую функцию и ограничения:

Целевая функция.

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

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

2 Теоретическая часть

В данной работе решение примера осуществляется с помощью симплекс метода.

1. Симплекс метод

   1. Алгоритм симплекс-метода для задачи на минимум

Шаг 0: Подготовительный этап. Приводим задачу ЛП к специальной форме.

Шаг 1: Составляем симплекс-таблицу, соответствующую специальной форме:

	B		…		…
L			…		…
			…		…
..	..	…………
			…		…
..	..	…………
			…		…

Заметим, что этой таблице соответствует допустимое базисное решение задачи. Значение целевой функции на этом решении

Шаг 2: Проверка на оптимальность.

Если среди элементов индексной строки симплекс – таблицы нет ни одного положительного элемента то, оптимальное решение задачи ЛП найдено: .Алгоритм завершает работу.

Шаг 3: Проверка на неразрешимость.

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

Шаг 4: Выбор ведущего столбца q.

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

Шаг 5: Выбор ведущей строки p.

Среди положительных элементов столбца находим элемент , для которого выполняется равенство:

Строку p объявляем ведущей (разрешающей). Элемент объявляем ведущим (разрешающим).

Шаг 6: Преобразование симплексной таблицы.

Составляем новую симплекс-таблицу, в которой:

а) вместо базисной переменной записываем , вместо небазисной переменной записываем ;

б) ведущий элемент заменяем на обратную величину ;

в) все элементы ведущего столбца (кроме ) умножаем на ;

г) все элементы ведущей строки (кроме ) умножаем на ;

д) оставшиеся элементы симплексной таблицы преобразуются по следующей схеме «прямоугольника».

Из элемента вычитается произведение трех сомножителей:

первый - соответствующий элемент ведущего столбца;

второй - соответствующий элемент ведущей строки;

третий - обратная величина ведущего элемента .

Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».

Шаг 7: Переход к следующей итерации осуществляется возвратом к шагу 2.