 |
Линейного программирования
|
|
|
|
Наибольшее распространение в практике управления экономическими объектами имеютлинейные модели. Хотя среди задач поиска оптимального решения линейные задачи занимают малое место. Во-первых, большинство процессов в экономике имеют линейную природу и, следовательно, хорошо описываются линейными функциями. Исключением являются лишь накопление процентов на банковском счете и основанные на этом экспоненциальные процессы. Во-вторых, математическая постановка задачи линейной оптимизации хорошо изучена и не представляет научных проблем. Для практического применения в моделировании необходимо четко помнить фундаментальную теорему линейного программирования. Задача линейного программирования тогда и только тогда имеет решение, когда многогранник решений ограничен. Необходимо ясно представлять, когда решение единственно, не ограничено, не существует и имеется множество решений. Наиболее четкое представление всех возможных ситуаций дает графическая интерпретация в двухмерном пространстве. Все возможные семь исходов необходимо представлять каждому, кто составляет и решает задачи линейной оптимизации. Для нахождения оптимума линейной модели необходимо
1. Выразить критерий оптимальности в виде линейной целевой функции.
2. Ограничения, налагаемые на переменные, необходимо выразить в виде линейных неравенств.
Более современным средством для оптимизации линейных моделей является разработанных кампанией LINDO Systems, Inc пакет LINDO (L inear, IN teractive and D iscrete O ptimizer). Программный комплекс LINDO работает под управлением Windows и требует более 8 мегабайт дискового пространства.
При построении моделей исследователю необходимо последовательно пройти следующие этапы моделирования:
|
|
|
1. Постановка задачи и обоснование критерия оптимальности. На данном этапе необходимо сформулировать задачу, провести качественный и количественный анализ моделируемого объекта, оценить возможность сбора достоверной информации. Для выбора критерия оптимальности необходимо провести сравнение возможных критериев и выбрать соответствующий задачам эксперимента критерий.
2. Разработка структурной математической модели. На данном этапе производится выбор метода решения поставленной задачи, определяются учитываемые ограничения и участвующие в них переменные, производится унификация символики и подбираются аналоги в постановке задачи.
3. Сбор и обработка информации. Наиболее трудоемкий этап для большинства задач. Необходимо классифицировать и выверить собранную информацию, провести занесение ее в созданные базы данных, сформировать дубликаты баз, провести контрольное суммирование и т.д.
4. Построение числовой модели. Запись матрицы задачи в соответствии с принятыми обозначениями и с учетом единиц измерения для конкретной программы расчета на ЭВМ.
5. Решение задачи на ЭВМ. Включает в себя отладку, исправление синтаксических ошибок, контрольные прогоны задачи на известных тестовых примерах, получение исчерпывающей выходной информации на твердых носителях или в электронной форме на дискетах для чтения на своем компьютере в форме, удобной для представления отчета.
6. Анализ решения. Оценка адекватности полученного решения. Ретроспективные расчеты по модели, сопоставление с имеющимися результатами других исследователей, предыдущими данными, расчетами по другим моделям, экспертными оценками и т.д.
Постановка задачи сводится к переводу словесного описания ситуации в формализованное, в котором определяется переменная уравнения, ограничения и целевая функция. ЗЛП состоит в определении минимального или максимального значения целевой функции; целевая функция и ограничения и представляют собой линейные неравенства.
|
|
|
(F(х) = 
) ®Max (4.1)
i = 1….k (4.2)
xj ³ 0,
aij, bi, ci - заданные постоянные величины
Чтобы решить эту задачу, нужно найти такой вектор Х = (x1, x2,… xк)
(набор переменных величин xj), чтобы он доставлял максимальное значение целевой функции F (х)
Пример постановки ЗЛП
На предприятии изготавливается два вида изделий из трёх видов материалов
aij – расход материала вида i на одно изделие j.
bi - запас материала вида i
ci - прибыль от одного изделия вида i.
Студентам необходимо сформулировать ЗЛП, чтобы определить: Сколько изделий каждого вида следует производить, чтобы максимизировать прибыль. Расход материалов представлен в таблице 4.1.
Таблица 4.1
Расход материала вида i на одно изделие j
| Изделие (j) | Вид материала (i) | Прибыль на одно изделие | ||
| 1 | 2 | 3 | ||
| 1 | ||||
| 2 | ||||
| Запас материалов |
Решение:
В соответствии с вопросом, сформулированным в задаче, в качестве переменной величины выступит объём производства изделий каждого вида. Тогда:
Х1 - объём производства изделий 1-го вида
Х2 - объём производства изделий 2-го вида
Постановка задачи ЛП:
22Х1 + 14Х2 ® мах (максимизировать совокупную прибыль от производства изделий обоих видов)
5 Х1 + 7 Х2 £ 456 – ограничение на потребление материалов 1-го вида
2 Х1 + 8 Х2 £ 594 - ограничение на потребление материалов 2-го вида
6 Х1 + 4 Х2 £ 872 - ограничение на потребление материалов 3-го вида
Х1, Х2 ³ 0 - изделия должны производиться
Вариант 1.
В трёх ателье изготавливаются два фасона пальто.
aij – загрузка тканью j-го ателье при изготовлении пальто, %
ci - прибыль от одного пальто фасона i, руб.
Сформулировать ЗЛП, чтобы определить, сколько пальто каждого фасона следует изготавливать при возможно полной загрузке тканью ателье, чтобы получить максимальную прибыль. Загрузка тканью ателье представлена в таблице.1.
Таблица 1.
Загрузка ателье тканью для пальто
| Изделие (j) | № ателье(i) | Цена пальто | ||
| 1.2 | 5.1 | |||
| Максимальная загрузка | 100% | 100% | 100% |
|
|
|
Вариант 2
Имеются три склада компьютерных технологий А1, А2, А3 и три технических центра.
Ц1, Ц2, Ц3. На складах следующее число контейнеров: А1= 20 А2=6 А3 =14; в
Транспортные затраты aij на перевозку одного компьютера со i –го склада в магазин j представлены в таблице 2:
Таблица 2
Транспортные затраты
| Ц1 | Ц 2 | Ц3 | |
| А1 | 4(a12) | ||
| А2 | |||
| А3 |
Составить задачу линейного программирования (целевую функцию и ограничения)
Пояснение. В качестве переменной величины использовать Хij – число перевезённых компьютеров с i –го склада в магазин j
Вариант 3
Сформулировать ЗЛП, чтобы определить: Сколько услуг каждого вида следует предоставить, чтобы максимизировать прибыль. Расход материалов для оказания каждого вида услуг представлен в таблице 3.
Таблица 3
Расход материала вида i на одно изделие j
| Изделие (j) | Вид материала (i) | Прибыль на одно изделие | ||
| Запас материалов |
Вариант 4
Из двух складов А1 и А2 следует развести компьютеры по трём
магазинам В1, В 2, В3. На складах имеется: А1 =100, А2=80 компьютеров.
В магазинах требуется: В1=26, В 2=66, В3=44 компьютеров
Транспортные затраты aij на перевозку одного компьютера со i –го склада в магазин j представлены в таблице 4:
Таблица 4
Транспортные затраты
| В1 | В 2 | В3 | |
| А1 | 3(a12) | ||
| А2 |
Составить задачу линейного программирования (целевую функцию и ограничения)
Пояснение. В качестве переменной величины использовать Хij – число перевезённых компьютеров с i –го склада в магазин j.
Вариант 5
В ресторане японской кухни изготавливается два вида роллов из трех видов рыбы
aij – расход рыбы вида i на один ролл j.
bi - запас рыбы вида i
ci - прибыль от одного ролла вида i.
Сформулировать ЗЛП, чтобы определить: Сколько роллов каждого вида следует изготавливать, чтобы максимизировать прибыль. Расход рыбы представлен в таблице 5.
Таблица 5
Расход рыбы вида i на один ролл j
|
|
|
| Изделие (j) | Вид рыбы (i) | Прибыль на один ролл | ||
| Запас рыбы |
Вариант 6
В трех цехах по производству стоматологического оборудования изготавливаются два вида стоматологических кресла.
aij – загрузка j-го цеха при изготовлении стоматологических кресел, %
ci - прибыль от одного стоматологического кресла вида i, руб.
Сформулировать ЗЛП, чтобы определить: Сколько стоматологических кресел каждого вида следует производить при возможно полной загрузке цехов по производству стоматологического оборудования, чтобы получить максимальную прибыль. Загрузка цехов представлена в таблице 6.
Таблица 6
Загрузка цехов по производству стоматологического оборудования
| Изделие (j) | № цеха по производству стоматологического оборудования(i) | Цена стоматологического кресла | ||
| Максимальная загрузка | 100% | 100% | 100% |
Вариант 7.
Из двух складов автозапчастей А1 и А2 следует развести аккумуляторы для автомобилей по трём магазинам «Колесо». В1, В 2, В3. На складах имеется: А1 =35, А2=45 аккумуляторов для автомобилей.
В магазинах «Колесо» требуется: В1=16, В 2=36, В3=28 аккумуляторов
Транспортные затраты aij на перевозку одного аккумулятора с i –го склада в магазин j представлены в таблице 7:
Таблица 7
Транспортные затраты
| В1 | В 2 | В3 | |
| А1 | |||
| А2 |
Составить задачу линейного программирования (целевую функцию и ограничения)
Пояснение. В качестве переменной величины использовать Хij – число перевезённых аккумуляторов с i –го склада в магазин j
Вариант 8
В трёх компьютерных организациях изготавливаются два вида программ для компьютеров.
aij – загрузка j-ой компьютерной организации при изготовлении компьютерной программы, %
ci - прибыль от одной компьютерной программы вида i, руб.
Сформулировать ЗЛП, чтобы определить: Сколько компьютерных программ каждого вида следует производить при возможно полной загрузке компьютерных организаций, чтобы получить максимальную прибыль. Загрузка компьютерных организаций представлена в таблице 8.
Таблица 8
Загрузка компьютерных организаций
| Изделие (j) | № компьютерной организации(i) | Цена компьютерной программы | ||
| Максимальная загрузка | 100% | 100% | 100% |
Вариант 9
На предприятии изготавливается два вида изделий из трёх видов материалов
aij – расход материала вида i на одно изделие j.
bi -запас материала вида i
|
|
|
ci - прибыль от одного изделия вида i.
Сформулировать ЗЛП, чтобы определить, сколько изделий каждого вида следует производить, чтобы максимизировать прибыль. Расход материалов представлен в таблице 9.
Таблица 9
Расход материала вида i на одно изделие j
| Изделие (j) | Вид материала (i) | Прибыль на одно изделие | |
| Запас материалов |
Вариант 10
Из двух фармацевтических складов А1 и А2 следует развести коробки с лекарственными препаратами по трём поликлиникам В1, В 2, В3. На фармацевтических складах имеется коробок с лекарственными препаратами: А1 =65, А2=85
В поликлиники требуется: В1=36, В 2=66, В3=58 коробок с лекарственными препаратами
Транспортные затраты aij на перевозку одной коробки с лекарственными препаратами с i –го фармацевтического склада в поликлинику j представлены в таблице 10:
Таблица 10
Транспортные затраты
| В1 | В 2 | В3 | |
| А1 | |||
| А2 |
Составить задачу линейного программирования (целевую функцию и ограничения)
Пояснение. В качестве переменной величины использовать Хij – число перевезённых коробок с лекарственными препаратами с i –го фармацевтического склада в поликлинику j
ЗАДАНИЕ 5. ПРОЦЕДУРА ВЫБОРА ОБЪЕКТОВ ПО
МНОГОМЕРНЫМ КРИТЕРИЯМ
или метод попарного сравнения альтернатив (РИПСА)
Часто встречается задача, когда необходимо выбрать лучший объект из нескольких, при условии, что существует набор критериев, их оценки или объекта оцениваются несколькими экспертами.
Рассмотрим:
Е =еi, i=1,n – множество элементов
К =kj, j=1,n – множество критериев
αik – оценка, составленная еi по К
Рк – множество состояний объектов, который допускает критерий kj, имеет структуру шкалы.
По этим условиям можно сравнить объекты относительно одного критерия на основании сравнения их состояния, т.е. оценок, соответствующих этому критерию.
αik > αjk -,будет означать, что по критерию К объект еi предпочтительней, чем еj
еi >еj
Если оценки объектов по разным критериям противоречивы, то для сравнения таких объектов можно предложить процедуру, которая базируется на особых принципах. Согласно этой процедуре всё множество критериев К можно разделить на два подмножества.
Сij – множество критериев, согласно которым еi по крайней мере, не хуже чем еj
Dij – множество критериев, для которых это условие не выполняется.
Для начала процедуры сравнения объектов рассматривается гипотеза, что еi >еj. Для оценки соответствия различных критериев данной гипотезе вводится показатель соответствия сij
Он рассчитывается по формуле:
сij = 
(5.1)
Отношение суммы подтверждений этой гипотезы соответствия к сумме количества экспертов (число экспертов). Показатель соответствия рассчитывают для каждой пары объектов еi еj. Для осуществления процедуры сравнения необходимо учесть и критерии, противоречащие введённому предположению, что объект еi по крайней мере не хуже еj. С этой целью рассчитывается показатель не соответствия - сij (s)
Для его получения необходимо:
1. Вычислить разности между оценками объектов αik и αjk для всех КÎDij и упорядочить полученные отклонения (разности) в невозрастающую последовательность.
2. Определить показатель несоответствия как S-ый элемент построенной последовательности.
Пример: на предприятии проводится отбор платьев для массового пошива, при этом каждое платье оценивают по 6 показателям.
е1 - трудоёмкость процесса
е2 - удельная прибыль
е3- инвариантность тела ткани
е4 - инвариантность фурнитуры
е5 - величина охвата рынка
е6 - соотв. модной тенденции
Эти показатели получили оценки 10-ти специалистов по 10-ти бальной шкале. Экспертные оценки представлены в таблице 5.1:
Таблица 5.1
Оценки показателей экспертами
| показатели | эксперты | |||||||||
| е1 | ||||||||||
| е2 | ||||||||||
| е3 | ||||||||||
| е4 | ||||||||||
| е5 | ||||||||||
| е6 |
Задача состоит в выборе наиболее значимого элемента еi или группы этих элементов при разных предположениях относительно к требованиям к точности совпадения мнений этих экспертов. Посмотрим матрицу соответствия Сij =
Таблица 5.2
Матрица соответствия
| е1 | е2 | е3 | е4 | е5 | е6 | |
| е1 | х | 0,6 | 0,8 | 0,5 | 0,5 | 0,6 |
| е2 | 0,5 | х | 0,8 | 0,3 | 0,4 | 0,5 |
| е3 | 0,2 | 0,5 | х | 0,4 | 0,1 | 0,2 |
| е4 | 0,5 | 0,4 | 0,3 | х | 0,7 | 0,6 |
| е5 | 0,5 | 0,5 | 0,1 | 0,5 | х | 0,8 |
| е6 | 0,6 | 0,5 | 0,9 | 0,5 | 0,2 | х |
Гипотеза: еi >еj
| е1> е2 e1> е3 | e2 >е1 e2 >е3 e2 >е4 e2 >е5 e2 >е6 e2 >е |
Строим матрицу несоответствия: Dij =
Таблица 5.3
Матрица несоответствия
| е1 | е2 | е3 | е4 | е5 | е6 | |
| е1 | х | 0.4 | 0.7 | 0.5 | 0.9 | 0.8 |
| е2 | 0.7 | х | 0.5 | 0.5 | 0.7 | 0.6 |
| е3 | 0.6 | 0.5 | х | 0.5 | 0.7 | 0.5 |
| е4 | 0.5 | 0.5 | 0.5 | х | 0.5 | 0.7 |
| е5 | 0.7 | 0.7 | 0.7 | х | 0.8 | |
| е6 | 0.6 | 0.2 | 0.1 | 0.5 | 0.6 | х |
е1 > е2
[2,3,3,4] = [4.3.3.2]
d12(1) = 0.4
зафиксируем значение параметра S и зададим два числа:
c – пара соответствия
d – пара несоответствия
Будем считать, что согласно введенным критериям и парам c и d, если и только если пара (е1 , е2) приводит к показателю соответствия
сij≥с и dij(s)≤d – показатель несоответствия.
Предпочтения опр. т. обр. удобно представлять в виде графа, вершинами которого являются элементы Е= {еi} множества Е, а дуги выражают отношение предпочтения своим направлением от еi к еj , если еi > еj. Т.е. граф G(c,d,s)=[E,U(c,d,s)] множество Е, которое объединяет дуга. Очевидно, чем меньше требования к значениям c и d, тем богаче дугами соответствующий граф. Однако сравнение и выбор проводимые на основе очень малых требований могут не отразить реальную ситуацию выбора.
Поэтому необходимо последовательно и постепенно ослаблять требования к параметрам c,d,s и проанализировать возникающие связи.
Таким образом для каждой тройки c,d,s построенной граф, можно разделить на два непересекающихся подмножества.
Пусть 1-ое подмножество таково, что всякий элемент не включенный в него будет превзойден по крайней мере одним элементом ему принадлежащим.
Это свойство называется свойством внешней устойчивости.
Другое свойство данного подмножества в том, что никакой его элемент не превосходит другого элемента, т.е. они не сравнимы между собой при заданных параметрах c,d,s.
Подмножество вершин графа обладает этими 2-мя свойствами называется ядром.
Оно определяет набор лучших элементов или параметров.
c = 0,7
d = 0,4
e1, e2, e3, e4 – ядро
e2
e1 e3
e6 e4
e5
c = 0,6 d = 0,4 Ядро: e1, e3, e4
e2
e1 e3
e6 e4
e5
По условию задачи ядро графа с параметрами 0,6; 0,4; 1 содержит вершины e1, e3, e4.
Можно проследить такую цепочку e3 > e6 > e5.
Если требуется обогатить граф дугами, то из-за невозможности ослабить требования к порогам соответствия и несоответствия необходимо обратиться к измерению параметра S и рассчитать матрицу несоответствия Сij(2).
Ядро графа может иметь различное число элементов. Если в ядре очень много элементов, это означает, что антагонизм критериев таков, что не позволяет сравнивать объект при этих параметрах. Усиление требовательности к порогам c и d сократит число элементов в ядре. В результате анализа поведения графов и их ядер можно выбрать небольшое число объектов, среди которой находится и самый лучший. Иногда можно упорядочить объекты в некоторую последовательность, благодаря которой каждый объект сравнивается с другими и из них можно выбрать близкие или эквивалентные (циклически замкнутые) и прочие. Выбрать лучшие объекты (показатели) на основе построения ядра графа.
Вариант 1
|
|
|
