РГР Коробов

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

Реферат

Отчет по расчетно-графической работе 13 с., 1 ч., 8 рис., 1 табл., 1 источ.

ПРОДУКЦИЯ, ОПТИМИЗАЦИЯ, МАКСИМИЗАЦИЯ, ТОВАР, НОРМА РАСХОДА, СИМПЛЕКС-МЕТОД

Цель расчетно-графической работы – построение математической модели данной задачи и ее решение.

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

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

Содержание

Реферат 2

Введение 4

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

Расчетная часть. 8

Заключение 13

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

Введение

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

Фабрика может производить n различных продуктов, располагая для этого s видами ресурсов a1, …. as. Для производства продуктов могут быть использованы m технологических способов. Заданы величины с_kji, характеризующие нормы расхода i-го ресурса на единицу k-го продукта при изготовлении его j-м способом. Известна цена p_k – прибыль полученная от каждого k-го продукта.

Составить модель задачи по определению оптимального набора продуктов и способов их производства из условия максимизации товарной продукции при дополнительном условии, согласно которому любой k-й продукт либо должен производится в количестве, не меньшем d_k, либо совсем не производиться.

2. Параметры управления

В данной задаче неизвестным является количество определенного вида товара, изготовленным определенным технологическим способом X_kj. Очевидно, что переменная X_kj должна быть неотрицательна для любого k и для любого j. Необходим заранее неизвестный коэффициент y_k, относительно которого будет приниматься решение о производстве данного вида товара.

3. Условия

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

(1)

В данной задаче необходимо максимизировать прибыль от продажи продуктов. При этом целевая функция имеет вид:

(2)

Как видно из формул (1), (2) построенная задача относится к задачам линейного программирования.

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

Одним из численных методов решения задач линейного программирования является симплекс-метод. Предложенный еще Георгом Дантзигом в 1947 г. алгоритм симплексного метода является одним из самых ранних и наиболее известных методов оптимизации.

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

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

Рассмотрим задачу в произвольной форме:

L=p₁∙x₁₁+ p₁∙x₁₂+…+ p₁∙x_1m+ p₂∙x₂₁+ p₂∙x₂₂+…+ p₂∙x_2m + p_n∙x_n1+ p_n∙x_n2+…

+ p_n∙x_nm → max

x₁₁∙c₁₁₁+ x₁₂∙c₁₂₁+…+x_1m∙c_1m1+ x₂₁∙c₂₁₁+ x₂₂∙c₂₂₁+…+x_nm∙c_nm1≤a₁

x₁₁∙c₁₁₂+ x₁₂∙c₁₂₂+…+x_1m∙c_1m2+ x₂₁∙c₂₁₂+ x₂₂∙c₂₂₂+…+x_nm∙c_nm2≤a₂

……………

x₁₁∙c_11s+ x₁₂∙c_12s+…+x_1m∙c_1ms+ x₂₁∙c_21s+ x₂₂∙c_22s+…+x_nm∙c_nms≤a_s

x₁₁ ≥0, x₂₁ ≥0, …, x_n1 ≥0, …, x_nm ≥0

Преобразуем систему ограничений в систему уравнений:

x₁₁∙c₁₁₁+ x₁₂∙c₁₂₁+…+x_1m∙c_1m1+ x₂₁∙c₂₁₁+ x₂₂∙c₂₂₁+…+x_nm∙c_nm1+z₁=a₁

x₁₁∙c₁₁₂+ x₁₂∙c₁₂₂+…+x_1m∙c_1m2+ x₂₁∙c₂₁₂+ x₂₂∙c₂₂₂+…+x_nm∙c_nm2+z₂=a₂

……………

x₁₁∙c_11s+ x₁₂∙c_12s+…+x_1m∙c_1ms+ x₂₁∙c_21s+ x₂₂∙c_22s+…+x_nm∙c_nms+z_s=a_s

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

Таблица 1 – начальная симплекс таблица.

	A	x11	x21	x12	x22	…	xnm
L	0	-p1	-p2	-p1	-p2	…	-pn
z1	a1	c111	c211	c121	c221	…	cnm1
…	…	…	…	…	…	…
zs	as	c11s	c21s	c12s	c22s	…	cnms

Алгоритм решения данной задачи будет следующим:

Шаг 1. Составить симплекс-таблицу.

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

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

Шаг 3. Проверка на удовлетворительное оптимальное решение.

Если среди элементов оптимального решения нет ни одного неудовлетворяющего условию x_kj≥d_k то удовлетворительное оптимальное решение задачи ЛП найдено. Алгоритм завершает работу. Если существует хотя бы одно k, такое, что x_kj<d_k, тогда возвращаемся к шагу 1, где избавляемся от всех соответствующих x_k.

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

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

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

Среди элементов индексной строки симплекс – таблицы выбирается максимальный по модулю элемент.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Расчетная часть.

Для удобства расчетов создана программа. Программа написана на языке C#. Пронаблюдаем работу программы на примере. Главное окно программы представлено на рисунке 1.

Рисунок 1- Главное окно программы

Зададим в настройках следующие параметры: 2 вида товаров, 2 вида ресурсов, 2 вида технологических способов. Зададим величины ресурсов. И прибыль от каждого вида товара. Также заполним матрицы норм расхода ресурсов. Зададим минимально возможное количество выпускаемого товара. Соответствующие окна программы, с введенными значениями представлены на рисунках 2, 3, 4, 5, 6.

Рисунок 2- Окно настроек

Рисунок 3- Окно задания величины ресурсов

Рисунок 4- Окно задания величины прибыли

Рисунок 5- Окно задания норм расхода

Рисунок 6- Окно задания допустимого количества продукции

Для введенных значений, начальная симплекс-таблица, представлена на рисунке 7.

Рисунок 7- Начальная симплекс-таблица.

Найдем оптимальные решения.

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

Рисунок 8- Решения.

После нахождения первого решения, количество производимого товара 2 было неудовлетворительным, поэтому от его производства необходимо отказаться, тогда оптимальным будет производить 1 товар 1 технологическим способом.

Заключение

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

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

1.  Зыкина А.В. Математическое программирование: Учеб. пособие. – Омск : Изд-во ОмГТУ, 2000. –64 с.

14