Методическое пособие 577
.pdfВ. Н. Коровин
МЕТОДЫ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ В МЕДИЦИНЕ
Учебное пособие
Воронеж 2019
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Воронежский государственный технический университет»
В. Н. Коровин
МЕТОДЫ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ В МЕДИЦИНЕ
Учебное пособие
Воронеж 2019
1
УДК 681.3(075.8) ББК 32.96я7
К681
Рецензенты:
кафедра биомедицинской инженерии Юго-Западного государственного университета, г. Курск (зав. кафедрой д-р техн. наук, проф. Н. А. Кореневский);
д-р мед. наук, проф. Н. Е. Нехаенко
Коровин, В. Н.
Методы решения оптимизационных задач в медицине:
К681 учебное пособие / В. Н. Коровин; ФГБОУ ВО «Воронежский государственный технический университет». — Воронеж: Изд-во ВГТУ, 2019. — 82 с.
ISBN 978-5-7731-0833-7
Изучается задача производственного плана, ее решение симплексным методом, а также средствами EXCEL. Рассматривается целочисленное линейное программирование, решается задача о назначениях средствами EXCEL. Изучаются транспортная задача, задача коммивояжера и способы их решения. Описываются методы решения многокритериальных задач.
Издание предназначено для студентов направлений 12.03.04 «Биотехнические системы и технологии» (профили «Биотехнические и медицинские аппараты и системы», «Менеджмент и управление качеством в здравоохранении») и 12.04.04 (программа магистерской подготовки «Интеллектуальные системы управления в здравоохранении») очной и заочной форм обучения.
Ил. 39. Табл. 72. Библиогр.: 1 назв.
УДК 681.3(075.8) ББК 32.96я7
Печатается по решению учебно-методического совета Воронежского государственного технического университета
ISBN 978-5-7731-0833-7 © Коровин В. Н., 2019
©ФГБОУ ВО «Воронежский государственный технический университет», 2019
2
ВВЕДЕНИЕ
Современное управление, требующее принятия решений, имеющих не только большое стоимостное выражение, но и различные социальные последствия, должно быть обеспечено разнообразным инструментарием, позволяющим осуществлять выбор из имеющихся вариантов, если не наилучшего решения, то, во всяком случае, предпочтительного с точки зрения лица принимающего решение. Необходимость изучения методов оптимизации и теории принятия решений в инженерных направлениях и специальностях обусловлена как минимум двумя факторами. Во-первых, большинство специалистов рано или поздно становятся руководителями и, следовательно, вынуждены принимать управленческие решения. Во-вторых, инженерная деятельность предполагает принятие многочисленных технических и технологических решений (при проектировании наилучшей конструкции медицинской техники, в случае выбора оптимальной последовательности обработки потоков задач и оптимального режима функционирования медицинских аппаратов и систем и во многих других ситуациях). Сегодня оптимизационные задачи и задачи принятия решений моделируются и решаются в самых различных областях техники. Существенно значение оптимизации и для медицины.
Учебное пособие имеет следующую структуру.
В первой главе рассматривается задача производственного плана и ее решение симплексным методом. Вторая глава посвящена решению задачи производственного плана средствами EXCEL. В третьей главе рассматривается целочисленное линейное программирование и решается задача о назначениях средствами EXCEL. Четвертая глава посвящена транспортной задаче и способам ее решений. Пятая глава анализирует задачу коммивояжера, алгоритм ее решения и оптимизации. Шестая глава посвящена методам решения многокритериальных задач. В конце каждой главы представлены контрольные вопросы, призванные закрепить пройденный материал.
3
ГЛАВА 1. РЕШЕНИЕ ЗАДАЧ ПРОИЗВОДСТВЕННОГО ПЛАНА СИМПЛЕКСНЫМ МЕТОДОМ
Задача производственного плана состоит в определении количества производимого товара для получения максимальной прибыли. В случае если ресурсы не ограничены, то решение задачи не представляет сложностей: больше производится — больше прибыль. Но если видов производимой продукции даже не два, а три, четыре или больше. А еще предприятие может быть ограничено в ресурсах. То есть известны значения каждого из ресурсов, которое нельзя превысить. Причем ресурсами могут выступать различные показатели: затраты времени, сырье (металлы, дерево, пластмассы, керамика и т.д.), финансы, информация и т.п.
Для производства одной единицы продукции каждого вида товара требуется определенное количество ресурсов. И эти значения для всех видов продукции известны. А еще известны прибыли от реализации единицы товара каждого вида.
Рассмотрим пример. Компания выпускает три вида медицинской техники: гальванизаторы, аппараты для дарсонвализации и УВЧ аппараты. Прибыль от реализации одного гальванизатора, так же как и от одного УВЧ-аппарата, составляет 4 тысячи рублей. Прибыль от реализации одного аппарата для дарсонвализации составляет 5 тысяч рублей.
Для производства гальванизаторов, УВЧ и «Дарсонваль»- аппаратов требуются трансформаторы, фильтры и усилители. Будем считать, что стоимость различных трансформаторов равна. Равна стоимость и различных фильтров. Аналогично и для усилителей. Для производства одного гальванизатора требуется 2 трансформатора, 4 фильтра и 4 усилителя. Для производства одного аппарата для дарсонвализации требуется 3 трансформатора, 2 фильтра и 4 усилителя. Для производства одного УВЧ-аппарата требуется 6 трансформаторов, 4 фильтра и 8 усилителей. Общее количество трансформаторов равно 240. Всего имеется 200 фильтров. Запас усилителей производится — 160.
4
Требуется определить, в каком количестве производить аппараты для терапии, чтобы получить максимальную прибыль. Симплекс-метод подходит для решения таких задач. Его алгоритм состоит в следующем:
–определяется первоначальный опорный план (составляется математическая модель, она приводится к каноническому виду, выбираются базисныепеременные);
–составляется симплекс таблица (первый столбец соответствует базисным переменным, второй производится — коэффициентам при целевой функции, третий производится — правым частям ограничений, последующие заполняются коэффициентами при соответствующих переменных в каждом из ограничений задачи);
–проверка плана на оптимальность. Для этого определя-
ются оценки i cij xj cj. В случае если все оценки отрицательные или равны нулю, то оптимальный план найден
имы нашли решение (решение находится в столбце b). Если среди оценок есть положительные, то план не оптимальный
изадачу необходимо оптимизировать;
–среди положительных оценок выбирается максимальная, и этот столбец объявляется ведущим;
–только среди положительных коэффициентов ведущего столбца определяются соотношения правых частей ограничений к соответствующим положительным коэффициентам. Среди этих отношений выбирается минимальное, и соответствующая строка объявляется ведущей. На пересечении ведущего столбца и ведущей строки находится ведущий элемент;
–пересчет симплекс таблицы: ведущая строка делится на ведущий элемент (начиная со столбца b), вся остальная часть таблицы пересчитывается по правилу «прямоугольника». Для того чтобы определить значение элемента в новой таблице по этому правилу, нужно найти отношение разности произведений диагонали, составленной из ведущего элемента и самого элемента в предыдущей таблице и другой диагонали (чтобы получился прямоугольник в таблице) к ведущему элементу.
5
Мы в дальнейшем более подробно изучим это правило на примере;
– переход к третьему шагу (пересчет оценок для новой таблицы и определения плана на оптимальность).
Составим из исходных данных математическую модель задачи. Целевая функция принимает следующий вид:
F(X) = 4x1 + 5x2 + 4x3 → max.
Система ограничений представляет собой
2x1 + 3x2 + 6x3 ≤ 240 4x1 + 2x2 +4x3 ≤ 200 4x1 + 6x2 + 8x3 ≤ 160.
Приведем математическую модель к канонической форме. Если целевая функция стремилась к максимуму, то она
приводится к минимуму умножением на –1. Если в правых частях ограничений есть отрицательные числа, то соответ-
ствующие ограничения умножаются на –1, соответственно меняются и знаки неравенств на противоположные. Далее избавляются от знаков неравенств: если стоял знак ≤, то к соответствующему ограничению прибавляется новая дополнительная переменная, а если был знак ≥, то новая дополнительная переменная вычитается. Так как этих дополнительных переменных нет в целевой функции, то на общую прибыль они не будут нести влияния.
F(X) = −4x1 − 5x2 − 4x3 → min;
2x1 + 3x2 + 6x3+ x4 = 240 4x1 + 2x2 +4x3+ x5 = 200 4x1 + 6x2 + 8x3+ x6 = 160.
Как видно, базисными переменными являются x4, x5 и x6. Составим первую симплекс таблицу (табл. 1).
6
|
|
Первоначальный опорный план |
|
Таблица 1 |
||||||
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-4 |
-5 |
-4 |
0 |
0 |
|
0 |
|
Базис |
С |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x6 |
|
x4 |
0 |
240 |
2 |
3 |
6 |
1 |
0 |
|
0 |
|
x5 |
0 |
200 |
4 |
2 |
4 |
0 |
1 |
|
0 |
|
x6 |
0 |
160 |
4 |
6 |
8 |
0 |
0 |
|
1 |
|
F |
|
0 |
4 |
5 |
4 |
0 |
0 |
|
0 |
|
Далее определим оценки — последняя строка таблицы.
Например, оценка для переменной x1: 0*2+0*4+0*4–(–4) = 5. У нас получилось три положительных оценки. Выбираем максимальную (5). Значит, столбец x2 является ведущим. Определим ведущую строку, для чего найдем соотношения: 240:3 = 80, 200:2 = 100, 160:6 ≈ 26,7. Поэтому третья строка (x6)
является ведущей, так как именно в ней отношение получилось минимальным. Значит, выделенный элемент (6) является ведущим. Далее пересчитываем таблицу по правилу «прямоугольника» (табл. 2). Ведущую строку делим на ведущий
элемент: 4:6 = 23 ; 6:6 1; 8:6 43 и т.д. Значения элементов
в новой таблице лучше оставлять в виде неправильных дробей, а не десятичных или смешанных чисел, так как в этом случае расчет окажется проще и быстрее в дальнейшем. Рассмотрим правило «прямоугольника» на некоторых элементах таблицы:
например, первая строка, столбец b: |
240 6 160 3 |
160 или |
|||
|
4 6 2 8 |
|
4 |
6 |
|
вторая строка, столбец x3: |
|
, или вторая строка, |
|||
|
6 |
|
3 |
|
|
столбец x5: 0 6 2 1 1.
6 3
Аналогично рассчитали и остальные элементы таблицы. Так как ведущий элемент находился на пересечении
строки x6 и столбца x2, то во второй таблице в качестве базисной переменной переменная x2 заменит переменную x6.
7
Таблица 2 Таблица, пересчитанная по правилу «прямоугольника»
|
|
|
-4 |
-5 |
-4 |
0 |
0 |
0 |
Базис |
С |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x4 |
0 |
160 |
0 |
0 |
2 |
1 |
0 |
-1/2 |
x5 |
0 |
440/3 |
8/3 |
0 |
4/3 |
0 |
1 |
-1/3 |
x2 |
-5 |
80/3 |
2/3 |
1 |
4/3 |
0 |
0 |
1/6 |
F |
|
-400/3 |
2/3 |
0 |
-8/3 |
0 |
0 |
-5/6 |
По известному нам правилу мы рассчитали оценки для второй таблицы. Среди этих оценок есть положительная (2/3). Значит, столбец x1 является ведущим. Определим ведущую строку, для чего найдем соотношения к положительным элементам этого столбца: 440/3:8/3 = 58, 80/3:2/3 = 40. Поэтому третья строка (x2) является ведущей, так как именно в ней отношение получилось минимальным. Значит, выделенный элемент (2/3) является ведущим. Далее пересчитываем таблицу по правилу «прямоугольника» (табл. 3).
Таблица 3 Таблица, пересчитанная по правилу «прямоугольника»
на второй итерации
|
|
|
-4 |
-5 |
-4 |
0 |
0 |
0 |
Базис |
С |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x4 |
0 |
160 |
0 |
0 |
2 |
1 |
0 |
-1/2 |
x5 |
0 |
40 |
0 |
-4 |
-4 |
0 |
1 |
-1 |
x1 |
-4 |
40 |
1 |
3/2 |
2 |
0 |
0 |
1/4 |
F |
|
-160 |
0 |
-1 |
-4 |
0 |
0 |
-1 |
Рассчитаем для этой таблицы оценки. Среди оценок нет положительных. Значит, мы нашли оптимальный план задачи. Решение находится в столбце b: x4 = 160; x5 = 40; x1 = 40. Все остальные переменные (x2, x3 и x6) приравниваются к нулю. Теперь подставим значения для найденных переменных в целевую функцию и найдем ее значение 4*40 = 160. Оптимальный план можно записать так: x1 = 40, F(X) = 4*40 =160.
8
Вывод: необходимо производить только гальванизаторы (в количестве 40 штук) для получения максимальной прибыли.
Рассмотрим еще один пример. Компания производит три вида медицинской техники: ЭКГ (электрокардиограф), ЭЭГ (электроэнцефалограф) и ЭМГ (электромиограф). Прибыль от реализации одного ЭКГ составляет 6 тысяч рублей. Прибыль от реализации одного аппарата ЭЭГ составляет 5 тысяч рублей. Прибыль от реализации одного аппарата ЭМГ составляет 9 тысяч рублей.
Для производства ЭКГ, ЭЭГ и ЭМГ аппаратов требуются трансформаторы, фильтры и усилители. Будем считать, что стоимость различных трансформаторов равна. Равна стоимость и различных фильтров. Аналогично и для усилителей. Для производства одного ЭКГ требуется 5 трансформаторов, 1 фильтр и 4 усилителя. Для производства одного ЭЭГ требуется 2 трансформатора, 6 фильтров, а усилителей не требуется. Для производства одного ЭМГ требуется 3 трансформатора, 2 фильтра и 3 усилителя. Общее количество трансформаторов равно 25. Всего имеется 20 фильтров. Запас усилителей — 18.
Требуется определить, в каком количестве производить аппараты ЭКГ, ЭЭГ и ЭМГ, чтобы получить максимальную прибыль.
Составим из исходных данных математическую модель задачи. Целевая функция принимает следующий вид:
F(X) = 6x1 + 5x2 + 9x3 → max.
Система ограничений представляет собой:
5x1 + 2 x2 + 3x3 ≤ 25 x1 + 6x2 + 2x3 ≤ 20 4x1 + 3x3 ≤ 18.
|
Приведем математическую модель к канонической |
форме. |
|
|
Для этого если целевая функция стремилась к максимуму, |
то |
она приводится к минимуму умножением на –1. Если |
в |
правых частях ограничений есть отрицательные числа, то |
9