III. Порядок выполнения работы.

⇐ ПредыдущаяСтр 3 из 9Следующая ⇒

1. Внимательно изучить теоретический материал, обратив внимание на особенности составления модели задачи и ее окончательный вид (16).

2. На основании табл.1 по номеру варианта определить параметры d₁, d₂, r₁, r₂, r₃ и записать модель типа (1) ¸ (5).

3. Решить сформулированную задачу симплекс-методом (использовать пакет LINPR), либо графически.

4. Выполнить аналогичные (6) ¸ (14) преобразования и записать многоцелевую модель типа (16).

5. Считая Р₁ = 1000, Р₂ = 100, Р₃ = 10/4, Р₄ = 1 решить задачу симплекс-методом, проанализировать полученные результаты.

6. Решить задачу при Р₁ = 1000000, Р₂ = 10000, Р₃= 100/4, Р₄= 1.

7. С учетом двух результатов обосновать окончательное решение.

8. Выполнить экономический анализ выдвигаемых целевых требований по результатам решений.

Таблица 1.

№ п/п

d₁

d₂

r₁

r₂

r₃

IV. Контрольные вопросы.

1. Для каких задач следует использовать целевое программирование?

2. Чем отличается целевое программирование от стандартной процедуры линейного программирования?

3. Какие основные приемы используются для выражения целей задачи и построения математической модели?

4. Чему равна прибыль в рассматриваемой модели объекта, если обивочная ткань выпущена в объеме 50000 м, а плательная в объеме 17000 м?

5. Поясните смысл соотношения P₁ > > P₂ > > P₃ > > P₄.

6. Модернизируйте целевую функцию Z в модели (16), если прибыль от продажи метра обивочного материала составляет 17 (у.е.), а плательного – 34 (у.е).

7. Какой экономический и математический смысл вкладывается в переменную d₄⁺?

Практическое занятие №6

1. Цель и задачи работы

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

2. Краткие теоретические сведения

Допустим, что изделия a, b, c, d производятся четырьмя разными подразделениями фирмы. Предположим также, что для производства одной единицы продукции типа «а» требуется единиц продукции типа «b» и единиц продукции типа «с». Для производства одной единицы продукции типа «d» требуется единиц продукции типа «a», единиц продукции типа «с» и единиц продукции типа «b». Данная ситуация приводит к следующей задаче.

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

Введем следующие переменные: -количество планируемой продукции;

- объемы заказов;

- объемы готовой продукции.

Представим задачу в виде графа (рис. 1):

рис. 1. Модель системы в виде графа.

Выразим изделия через комплектующие:

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

при i=0 получаем:

Таким образом получено выражение структуры и объема заказа через исходные комплектующие «b» и «с».

Подсчитаем количество продукции типа «b» и «c», необходимые для реализации всех заказов:

- число единиц продукции типа «b», необходимое для реализации всего заказа;

- число единиц продукции типа «с».

Структурную схему системы можно представить следующим образом (рис. 2):

рис. 2. Структурная схема системы.

Если систему представить на макроуровне, то получаем модель «черного ящика» (рис.3):

Рис.3. Отображение системы на макроуровне.

Объемы заказов «Q» являются исходными для всех последующих рассуждений. Так как количество планируемой продукции должно превышать объёмы заказов, а объёмы готовой продукции занимают промежуточное положение, справедливы следующие соотношения:

Следующая задача связана с уточнением организационной и технологической специфики ситуации. Известно также, что около 5% произведенной продукции составляет брак, а 3 % приходят в негодность по организационным причинам (порчи при хранении, складировании, и т.д.). Объем заказов составляет: Q =110, Q=150, Q=50, Q=70 штук. Время обработки одной детали типа «b» составляет 10 минут, типа с - 6 минут. В распоряжении имеется 3 и 2 (для i=0) однотипных станка для производства деталей «b» и «с», работающих в 2 смены ( 2*8 часов), при этом заказ необходимо выполнить в течении 5 рабочих дней (1 неделя). Имеется возможность сбывать излишки продукта типа «a» и «d», приносящие прибыль соответственно = 10 долл/1 штук., = 17 долл/штук. Необходимо определить оптимальную программу выпуска деталей a, b, c, d, дающую максимальную прибыль.

Целевая функция может быть представлена в виде

. (1)

Учитывая структуру изделий , а также плановый заказ получим следующую систему ограничений:

(2)

Конкретные данные и оценки максимальной производительности станков, приводят к окончательным соотношениям:

(3)

где - коэффициенты учитывающие потери по организационным причинам и в связи с браком.

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

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

1. На основании таблицы 1 необходимо выразить каждое изделие через исходные комплектующие, учитывая двухуровневое вложение элементов системы (комплектующие - сборочные единицы - изделия).

2. Представить систему в виде структурной схемы, отметив модель состава и модели типа «черного ящика».

3. Записать соотношения и неравенства, отражающие объёмы продукции Q, P, U для каждого изделия.

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

5. На основании структуры заказа (табл. 2) и структуры изделий (табл. 1) записать левую часть ограничений типа (2), (3) относительно каждой исходной комплектующей.

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

7. Оценить логически возможность реализации плана и выпуска дополнительной продукции.

8. По полученной модели определить оптимальный план, используя пакет нелинейной (NLP) либо линейной (LINPR) оптимизации.

9. Используя количественные показатели выполнить качественный анализ системы.

Таблица 1.

№ п.п.	Структура изделий
	Номера изделий	исход-ные	структуры
						комплектующие	сборочных единиц
	количество комплектующих
	a	e	1a, 2b	1a, 2b, 3c	2b, 3c, 4d	a, b	c: (2a, 3b), d: (7a, 2b), e(1a, 2b, 1d)
	b	d	1a, 1b	2a, 3b, 1c	1d, 2e	a, b, c	d: (1a, 1b, 1c), e: (2d, 1a, 2b)
	c	e	1b, 2c	3e, 2c	1b, 2c, 1a	a, c, e	b: (1a, 2e)
	d	b	2d, 3c	1a, 2b	2b, 3e, 1c	c, e	a: (1c, 1e), d: (1c, 1b, 2e), b: (2c, 3e)
	e	a	3c, 1b	1e, 1b	1a, 2b, 3c	e, d	a: (1e, 1d), b: (1a, 2e), c: (1a, 2b, 1e, 2d)
	a	d	1a, 3e	2a, 3c	1a, 2b, 3c	a, c, d	b: (1c, 2d), e: (1a, 2b, 3d)
	b	e	2a, 3c	3c, 2e	1a, 2e	a, e, d	b: (1a, 2e, 3d), c: (2e, 1d)
	c	a	2a, 1c	3c, 1e	1a, 2e	a, b, c, d	e: (2a, 1b, 1c, 7d)
	d	e	1a, 2b	1c, 2d, 3e	7a, 8e	a, b, c, d, e	-
	e	c	1a, 1e	2b, 3e	2b, 7e	c, d, e	a: (1c, 2d), b: (3a, 1c, 2e)
	e	a	1c, 1b	1c, 7b	2e, 7a	d, e	a: (1d, 2e), b: (1a, 2d, 3e), c: (1a, 2b, 1d, 8e)
	d	b	1a, 2b	2e, 3d	1b, 1c, 2e	b, c, d, e	a: (1b, 2c, 3e)
	e	c	1a, 1b	3e, 2c	2b, 7c, 3e	a, c, e	b: (1a, 2c), d: (1a, 3b, 2c)
	b	d	4a, 4b	1a, 3b, 7e	5a, 6b, 7c	b, c, d	a: (2d, 3c), e: (1a, 3b, 8d)
	a	e	3a, 1b	1a, 2e	2c, 3d, 5e	c, d, e	a: (1d, 3c), b: (1a, 3e)
	d	a	1a, 3e	2a, 3e	1c, 1d, 8e	a, b	c: (1a, 2b), d: (1a, 4b, 2c), e: (2c, 3d, 7a)
	e	b	5d, 3c	1a, 7e	2b, 8d	b, c	a: (1b, 2c), d: (1a, 2b, 3c), e: (1a, 2d, 3c)
	a	c	1a, 2b, 3c	1b, 8c	1d, 3e	c, d	a: (1c, 2d), b: (1c, 3d), e: (2a, 3b, 1c, 1d)
	e	d	1d, 3e	1a, 2e	1a, 3b, 2c	d, e	a: (7c, 1d), b: (7c, 2d), c: (2a, 2b, 1d)
	c	e	2a, 4b, 7с	1d, 2e	2c, 3d	b, c, d, e	a: (1b, 2c, 3d, 7e)
	a	b	c	1a, 2b	1c, 7d, 8e	a, c, d, e	b: (1a, 2c, 1d, 8e)
	a	e	b	2e, 7d	1a, 5b, 6c	a, b, c, d	e: (7a, 6b, 5c, 4d)
	b	c	d	1d, 8e	1b, 7c, 5e	a, b, c, e	d: (1a, 7b, 2c, 3e)
	e	d	b	5c, 6d, 1e	1c, 1e	a, b, c, d, e	-
	e	c	a	1c, 5e	1a, 2b, 3c	c, d, e	a: (1c, 2d), b: (3a, 1c, 2d, 7e)

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

где - неизвестные количества дополнительной продукции, ПОП -потери по организационным причинам.

Таблица 2.

№ п.п.	количество станков по комплектующим (время обработки - мин./дет.)	К_исп
	a	b	c	d	e
	5(10)	2(15)	-	-	-	0.7
	1(10)	3(20)	2(15)	-	-	0.8
	3(15)	-	2(10)	-	2(10)	0.9
	-	-	3(15)	-	3(7)	0.7
	-	-	-	2(10)	3(20)	0.85
	3(20)	-	2(15)	3(10)	-	0.9
	2(30)	-	-	2(15)	1(15)	0.6
	2(15)	1(10)	2(10)	3(20)	-	0.75
	2(15)	1(10)	2(7)	2(20)	2(30)	0.85
	-	-	3(30)	2(20)	1(10)	0.9
	-	-	-	2(15)	2(20)	0.75
	-	1(10)	2(20)	2(15)	2(20)	0.8
	2(15)	-	2(20)	-	2(15)	0.7
	-	3(30)	2(15)	2(10)	-	0.9
	-	-	3(20)	1(15)	2(30)	0.85
	2(15)	3(20)	-	-	-	0.8
	-	3(15)	3(10)	-	-	0.6
	-	-	3(15)	4(30)	-	0.7
	-	-	-	4(10)	3(15)	0.8
	-	2(10)	2(15)	2(20)	2(15)	0.9
	1(5)	-	2(15)	1(5)	2(20)	0.75
	2(10)	2(15)	3(30)	2(20)	-	0.9
	2(15)	1(5)	2(20)	-	1(5)	0.95
	5(30)	3(20)	2(10)	1(10)	1(10)	0.5
	-	-	3(15)	3(20)	4(15)	0.7

Таблица 3

№ п.п.

Структура заказа по изделиям (Q)

Количество смен (шт.)

Время выполнения заказа.

Прибыль от реализации дополнительной продукции (m)

Брак (%)

ПОП (%)

M_a

M_b

M_c

M_d

M_e

4. Контрольные вопросы

1. Отметьте модели «черного ящика», состава и структуры, представленные на рисунке 2.

2. В чем отличие модели структуры от структурной схемы системы?

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

4. Поясните характер целевой функции и ограничений задачи, к какому классу математических задач относится полученная модель?

5. Каким образом оцениваются правые части системы ограничений?

6. Проанализируйте адекватность рассматриваемой модели. Какие недостатки она содержит? Какие дополнения приводят к более точному отображению действительности?

Практическое занятие №7

Компромиссы Парето

I. Цель работы.

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

II. Краткие теоретические сведения.

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

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

Предположим, что мы сделали некоторый выбор. Обозначим его через х* и предположим, что существует некоторый другой выбор такой, что для всех критериев fi(x) имеют место неравенства

(1)(3.10)

причем хотя бы одно из неравенств — строгое.

Очевидно, что выбор предпочтительнее х*. Поэтому все векторы х*, удовлетворяющие (1), следует сразу исключить из рассмотрения. Имеет смысл заниматься сопоставлением, подвергать неформальному анализу только те векторы х*, для которых не существует такого, что для всех критериев удовлетворяются неравенства (1). Множество всех таких значений называют множеством Парето, а вектор х* называют неулучшаемым вектором результатов (вектором Парето), еслииз для любого i следует .

Предположим, что цели субъекта определяются двумя однозначными функциями:

Тогда каждому допустимому значению переменной x отвечает одна точка на плоскости ( ) (рис. 1) и равенства

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

Из тех же соображений должен быть исключен участок а'b, поскольку для каждой его точки е найдется точка, принадлежащая участку cd, в которой значения обеих функций и больше, чем в точке е. Значит, претендовать на принадлежность к множеству Парето могут только участки аа' и cd, причем точка а' также должна быть исключена.

Рисунок 1 – Отображение решений в плоскости критериев

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

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

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

Проектировщик оказывается перед необходимостью искать компромисс. И одним из путей отыскания этого компромисса будет построение множества Парето, изучение которого дает большую информацию. Лицо, принимающее решение, видит, в частности, сколько «стоит» увеличение одного из показателей, как оно сказывается на остальных показателях, значения которых непременно ухудшаются. Это множество оказывается, как правило, весьма сложной природы. Его анализ интуитивными методами вряд ли возможен.

Но, помимо критериев fi(x), достаточно часто в распоряжении проектировщика есть еще некоторый общий критерий F(x). Иногда он бывает формализован, записан в явном виде. Например, таким критерием может быть стоимость проекта. В этом случае исследователю операций представляется возможность решить задачу до «конца». Для этого ему достаточно определить вектор х, который дает решение задачи: F(x) max при х , где — множество Парето для функций , ..., f_n на множестве G допустимых векторов х. Например, в случае водохозяйственного комплекса множество G определяется таким распределением воды по объектам xi, при котором ее количество не превосходит притока Q(x).

Введение «общего» критерия F(x) и максимизация его значении на множестве Парето также является некоторой гипотезой, поскольку из совокупности критериев , ..., f_n, F один из критериев мы специальным образом выделяем.

⇐ Предыдущая 1 234 5 6 7 8 9 Следующая ⇒