- •ВВЕДЕНИЕ
- •1.1. Формулировка задачи линейного программирования
- •1.2. Распределение специализированных бригад скорой помощи по категориям больных
- •1.3. Некоторые другие задачи на распределение
- •1.4. Разработка комплексной лекарственной терапии
- •1.5. Выработка оптимального плана массового лечения
- •1.6. Определение линейных разделяющих функций
- •2.1. Метод динамического программирования
- •2.4. Выравнивание символьных последовательностей
- •3. ПРИМЕНЕНИЕ ТЕОРИИ ИГР ДЛЯ ОПТИМИЗАЦИИ КЛИНИЧЕСКИХ РЕШЕНИЙ В ХИРУРГИИ
- •3.1. Игры и методы их решения
- •3.2. Элементы теории статистических решений
- •3.3. Критерии принятия решений в условиях неопределенности
- •3.4. Принятие решений при острых хирургических заболеваниях органов брюшной полости
- •3.5. Минимизация риска хирургического вмешательства в онкологии
- •Список литературы
- •ПРИЛОЖЕНИЯ
Федеральное агентство по образованию
–––––––––––––––––––––––––––––––––––––
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»
–––––––––––––––––––––––––––––––––––––
А. П. НЕМИРКО, Л. А. МАНИЛО
МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ В ДИАГНОСТИКЕ И УПРАВЛЕНИИ СОСТОЯНИЕМ ЧЕЛОВЕКА
Учебное пособие
Санкт-Петербург
2009
1
УДК 519.8:61(07)
ББК Р.с11я7
Н 50
Немирко А. П., Манило Л. А.
Н50 Методы исследования операций в диагностике и управлении состоянием человека: Учеб. пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2009.
96 с.
ISBN 5-7629-0948-4
Посвящено вопросам применения математических методов для обоснования решений в задачах организации здравоохранения, диагностики и управления состоянием человека.
Предназначено для бакалавров и магистров направления подготовки 200300 (553400) – «Биомедицинская инженерия».
.
УДК 519.8:61(07)
ББК Р.с11я7
Рецензенты: каф. информатики и управления в медицинских системах СПбМАПО; канд. техн. наук К. М. Матус.
Утверждено редакционно-издательским советом университета
в качестве учебного пособия
ISBN 5-7629-0948-4 |
© СПбГЭТУ «ЛЭТИ», 2009 |
2
ОГЛАВЛЕНИЕ |
|
Введение................................................................................................................... |
4 |
1. Оптимизация принятия решений в АСУ здравоохранения методом |
|
линейного программирования............................................................................... |
6 |
1.1. Формулировка задачи линейного программирования ............................ |
6 |
1.2. Распределение специализированных бригад скорой помощи |
|
по категориям больных..................................................................................... |
11 |
1.3. Некоторые другие задачи на распределение........................................... |
15 |
1.4. Разработка комплексной лекарственной терапии .................................. |
17 |
1.5. Выработка оптимального плана массового лечения.............................. |
18 |
1.6. Определение линейных разделяющих функций..................................... |
22 |
2. Управление состоянием организма в биотехнических системах |
|
на основе динамического программирования.................................................... |
34 |
2.1. Метод динамического программирования.............................................. |
34 |
2.2. Управление переходом организма из начального в конечное |
|
состояние при наличии промежуточных состояний ..................................... |
38 |
2.3. Управление переходом организма в нормальное состояние |
|
в условиях неопределенности.......................................................................... |
46 |
2.4. Выравнивание символьных последовательностей................................. |
54 |
3. Применение теории игр для оптимизации клинических решений |
|
в хирургии.............................................................................................................. |
64 |
3.1. Игры и методы их решения....................................................................... |
64 |
3.2. Элементы теории статистических решений............................................ |
68 |
3.3. Критерии принятия решений в условиях неопределенности................ |
72 |
3.4. Принятие решений при острых хирургических заболеваниях |
|
органов брюшной полости............................................................................... |
74 |
3.5. Минимизация риска хирургического вмешательства в онкологии...... |
83 |
3.6. Решение игр m ×n ...................................................................................... |
85 |
Список литературы ............................................................................................... |
91 |
Приложения........................................................................................................... |
92 |
3
ВВЕДЕНИЕ
Автоматизация управления в здравоохранении призвана совершенствовать эту систему, улучшая качество обслуживания и снижая соответствующие затраты. В конечном счете эффект от автоматизации должен сказываться при достижении основных целей здравоохранения: предупреждении и ликвидации заболеваний, снижении смертности, улучшении физического развития, повышении трудоспособности и продолжительности жизни людей. В АСУ здравоохранения широко применяются методы математического моделирования, системного анализа, исследования операций [1], [2]. На верхних уровнях управления математические методы применяются для количественной оценки здоровья населения, рационального распределения ресурсов здравоохранения страны [1] и т. п. Средние уровни АСУ здравоохранения решают задачи организации здравоохранения в республиках, областях, городах и районах. Особенно важна рациональная организация управления на нижнем уровне, включающем в себя больницы, поликлиники, медсанчасти, диспансеры, аптеки и т. п.
Анализ процесса управления в АСУ позволяет выделить его три этапа: обработку информации об объекте управления (отображение информационного состояния), формирование управляющей функции (принятие решения) и реализацию функции управления. В высокоразвитых АСУ автоматизированы первые два из этих этапов. В АСУ здравоохранения среди задач, решаемых на этих этапах, особенно следует отметить задачи диагностики и управления состоянием организма. Это многочисленные задачи автоматизированной диагностики заболеваний и скрининг-анализа, принятие решений в клинике при лечении больных, управление состоянием организма в биотехнических системах [3], управление подготовкой спортсменов и т. д.
Применение ЭВМ для автоматизации принятия клинических решений открывает новые возможности в медицине, к которым относятся [4]:
•повышение точности клинической диагностики за счет систематичности и полноты используемых данных и возможности совместного применения данных из разных источников;
•повышение надежности клинических решений за счет более точной дифференциации сходных (но не идентичных) случаев и за счет использования четких и, следовательно, воспроизводимых критериев принятия решений;
4
•повышение эффективности медицинских диагностических тестов и лечебных процедур за счет сбалансированности затрат времени, денежных средств и причиняемых неудобств, с одной стороны, и ожидаемых результатов и риска при выполнении определенных действий, с другой;
•улучшение понимания структуры медицинских знаний и принципов принятия клинических решений.
Косновным методологическим подходам в области автоматизации принятия клинических решений относятся:
1)клинические алгоритмы (или протоколы), составляемые высококвалифицированными врачами и основанные на медицинской логике;
2)клинические банки данных, предусматривающие аналитическую обработку информации для определения прогноза и выбора метода лечения;
3)математические модели физиологических процессов;
4)статистические методы распознавания образов;
5)байесовский статистический подход [5];
6)методы исследования операций и теории решений;
7)формальные модели содержательных выводов – методы искусственного интеллекта.
В данной работе в качестве математической основы оптимизации принятия решений в АСУ здравоохранения рассмотрены три модели исследования операций: линейное программирование, динамическое программирование, теория игр и статистических решений. Изложение основано на описании примеров использования этих методов при решении различных задач организационного управления (массовое медицинское обследование, скорая помощь), оптимизации терапевтических воздействий при лечении больных, обоснования клинических решений в хирургии, нормализации состояния че- ловека-оператора. Методической основой изложения теоретических вопросов явились прекрасные руководства по исследованию операций Е. С. Вентцель [6], [7]. Приведенные примеры в основном носят учебный характер и могут использоваться как для иллюстрации лекционного материала, так и при решении конкретных задач на практических занятиях. С точки зрения практического применения исключение составляет раздел 3, в котором описаны методы обоснования решений в хирургии. Материал этого раздела основан на работе Г. А. Хая [8] и содержит алгоритмы принятия решений, применяемые непосредственно в клинической практике.
5
1.ОПТИМИЗАЦИЯ ПРИНЯТИЯ РЕШЕНИЙ
ВАСУ ЗДРАВООХРАНЕНИЯ МЕТОДОМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
1.1.Формулировка задачи линейного программирования
Любая задача линейного программирования (ЛП) может быть сведена к его основной задаче, формулируемой математически следующим образом. Имеется ряд переменных x1, x2, , xn . Требуется найти такие неотрицатель-
ные значения этих переменных, которые бы удовлетворяли системе линейных уравнений:
a11x1 +a12x2 + +a1n xn = b1; |
|
|
a21x1 +a22x2 + +a2n xn = b2 |
; |
(1.1) |
................................................. |
|
|
|
|
|
am1x1 +am2x2 + +amn xn = bm |
|
|
и, кроме того, обращали бы в минимум линейную функцию |
|
|
L = c1x1 + c2x2 + + cnxn, |
|
(1.2) |
где a11, a12, , amn; c1, c2, , cn – заданные постоянные коэффициенты. Очевидно, случай, когда линейную функцию нужно обратить не в ми-
нимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию
L′= −L = −c1x1 −c2x2 − −cn xn.
Допустимым решением основной задачи ЛП называют любую совокупность переменных
x1 ≥ 0, x2 ≥ 0, , xn ≥ 0 ,
удовлетворяющую уравнениям (1.1).
Оптимальным решением называется то из допустимых решений, при котором линейная функция (1.2) обращается в минимум.
Основная задача ЛП необязательно должна иметь решение. Может оказаться, что уравнения (1.1) противоречат друг другу; может оказаться, что они имеют решение, но не в области неотрицательных значений x1, x2, , xn . Тогда основная задача ЛП не имеет допустимых решений.
Наконец, может оказаться, что допустимые решения основной задачи ЛП существуют, но среди них нет оптимального: функция L в области допустимых решений не ограничена снизу.
6
Рассмотрим вопрос о существовании допустимых решений основной задачи ЛП. Для его решения можно исключить из рассмотрения линейную функцию L , которую требуется минимизировать, – наличие допустимых решений определяется только уравнениями (1.1). Остановимся на некоторых положениях линейной алгебры, рассматривающих этот вопрос.
Матрицей системы линейных уравнений (1.1) называется таблица, со-
ставленная из коэффициентов при x1, |
x2, , xn : |
|
||||||
|
|
a11 |
a12 |
a1n |
|
|
|
|
|
|
|
|
|||||
|
|
a21 |
a22 |
|
a2n |
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
am1 |
am2 |
amn |
|
|
|
Расширенной матрицей системы линейных уравнений называется та же матрица, дополненная столбцом свободных членов:
a11 |
a12 |
a1n |
b1 |
a21 |
a22 a2n |
b2 . |
am1 am2 amn bm
Рангом матрицы называется наибольший порядок отличного от нуля определителя, который можно получить, вычеркивая из матрицы какие-то строки и какие-то столбцы.
В линейной алгебре доказывается, что для совместности системы линейных уравнений (1.1) необходимо и достаточно, чтобы ранг матрицы системы был равен рангу ее расширенной матрицы. Этот общий ранг r называется рангом системы: он представляет собой число линейно независимых уравнений среди наложенных ограничений.
Очевидно, ранг системы r не может быть больше числа уравнений m :
r ≤ m.
Очевидно также, что ранг системы не может быть больше общего числа переменных n :
r ≤ n .
Ранг матрицы системы определяется как наибольший порядок определителя, составленного из элементов матрицы; так как число ее строк равно m , то r ≤ m ; так как число ее столбцов равно n , то r ≤ n .
7
Структура задачи линейного программирования существенно зависит от ранга системы ограничений (1.1). Рассмотрим прежде всего случай, когда r = n , т. е. когда число линейно независимых уравнений, входящих в систему (1.1), равно числу переменных n . Если отбросить уравнения, являющиеся линейными комбинациями других, система уравнений-ограничений основной задачи ЛП принимает вид
a11x1 +a12x2 + a1i + +a1n xn = b1; |
|
|
|||||||
a21x1 +a22x2 + a2i + +a2n xn = b2 |
; |
(1.3) |
|||||||
............................................................. |
|
||||||||
|
|
||||||||
an1x1 +an2 x2 + ani + +ann xn = bn. |
|
||||||||
Так как r = n , то определитель, составленный из коэффициентов, |
|
||||||||
|
a11 a12 a1i |
a1n |
|
|
|
|
|||
|
|
|
|
||||||
∆ = |
a21 a22 |
a2i |
a2n |
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|||||
|
an1 an2 ani |
ann |
|
|
|
|
не равен нулю. В этом случае система (1.3) имеет единственное решение. Чтобы найти величину xi , достаточно в определителе ∆ заменить i -й столбец столбцом свободных членов и разделить его на ∆.
Итак, при r = n система уравнений-ограничений основной задачи ЛП имеет единственное решение x1, x2, , xn . Если в этом решении хотя бы одна из величин x1, x2, , xn отрицательна, это означает, что полученное решение недопустимо и, значит, основная задача ЛП не имеет решения.
Если все величины x1, x2, , xn неотрицательны, то найденное решение является допустимым. Оно же является и оптимальным (потому что других нет).
Очевидно, что этот тривиальный случай не представляет интереса. Поэтому будем рассматривать только случай, когда r < n , т. е. когда число независимых уравнений, которым должны удовлетворять переменные x1, x2, , xn , меньше числа самих переменных. Тогда, если система сов-
местна, у нее существует бесчисленное множество решений. При этом n −r переменным (называемым свободными переменными) можно придавать произвольные значения, а остальные r переменных выразятся через них (эти r переменных называются базисными переменными).
8
Вообще, если ранг системы уравнений основной задачи ЛП (т. е. число линейно независимых уравнений, входящих в систему ограничений) равен r , то всегда можно выразить какие-то r базисных переменных через n −r остальных (свободных) и, придавая свободным переменным любые значения, получить бесчисленное множество решений системы.
При записи ограничений основной задачи ЛП в виде системы линейно независимых уравнений ранг системы r будет равен числу уравнений m .
Итак, если число уравнений основной задачи ЛП r = m меньше, чем число переменных n , то система линейных уравнений имеет бесчисленное множество решений, т. е. совокупностей значений x1, x2, , xn , удовлетво-
ряющих уравнениям-ограничениям (1.1). Если среди этих решений нет ни одного, для которого все x1, x2, , xn неотрицательны, это значит, что ос-
новная задача ЛП не имеет допустимого решения.
Если же существуют какие-то решения системы (1.1), для которых все x1, x2, , xn неотрицательны, то каждое из них допустимо. Возникает задача – найти среди допустимых решений оптимальное, т. е. такое решение x1, x2, , xn , для которого линейная функция (1.2) обращается в минимум.
Существует общий, часто применяемый симплекс-метод решения основной задачи ЛП, направленный на отыскание оптимального решения, но для частных задач (например, транспортных) существуют более простые методики [7]. Если число переменных n на 2 больше числа независимых уравнений m , которым они должны удовлетворять, т. е. если n −m = 2 , то можно решить задачу ЛП геометрическим способом.
На практике ограничения в задаче ЛП часто задаются не уравнениями, а неравенствами. Рассмотрим, как можно перейти от задачи с ограниченияминеравенствами к основной задаче ЛП.
Пусть имеется задача ЛП с n переменными x1, x2, , xn , в которой
ограничения, наложенные на эти переменные, имеют вид линейных неравенств. В некоторых из них знак неравенства может быть ≥, в других ≤ (второй вид сводится к первому переменой знака в обеих частях неравенства). Поэтому зададим все ограничения-неравенства в стандартной форме:
a11x1 +a12x2 + a1i + +a1n xn +b1 ≥ 0; |
|
|
a21x1 +a22x2 + a2i + +a2n xn +b2 ≥ 0; |
(1.4) |
|
..................................................................... |
||
|
||
am1x1 +am2x2 + ami + +amn xn +bm ≥ 0. |
|
9
Будем считать, что все эти неравенства линейно независимы (т. е. никакое из них нельзя представить в виде линейной комбинации других). Требуется найти такую совокупность неотрицательных значений x1, x2, , xn , ко-
торая удовлетворяла бы неравенствам (1.4), и, кроме того, обращала бы в минимум линейную функцию
L = c1x1 +c2x2 + +cn xn .
От задачи, поставленной таким образом, легко перейти к основной задаче ЛП. Введем обозначения:
y1 = a11x1 +a12 x2 + a1i + +a1n xn +b1; |
|
|
y2 = a21x1 +a22x2 + a2i + +a2n xn +b2; |
(1.5) |
|
........................................................................ |
||
|
||
ym = am1x1 +am2x2 + ami + +amn xn +bm , |
|
где y1, y2, , ym – некоторые новые переменные, которые принято называть добавочными. Согласно условиям (1.4), эти добавочные переменные так же, как и x1, x2, , xn , должны быть неотрицательными.
Таким образом, возникает задача линейного программирования в следующей постановке: найти такие неотрицательные значения n +m переменных x1, x2, , xn ; y1, y2, , ym , чтобы они удовлетворяли системе уравнений (1.5) и одновременно обращали в минимум линейную функцию этих переменных
L = c1x1 +c2x2 + +cn xn .
Как видно, перед нами в чистом виде основная задача ЛП. Уравнения (1.5) заданы в форме, уже разрешенной относительно базисных переменных y1, y2, , ym , которые выражены через свободные переменные
x1, x2, , xn . Общее число переменных равно n +m , из них n исходных
(свободных) и m добавочных. Функция L выражена только через свободные переменные (коэффициенты при добавочных переменных в ней равны нулю).
Таким образом, задача ЛП с ограничениями-неравенствами сведена к основной задаче ЛП, но с большим числом переменных, чем первоначально было в задаче.
Всегда возможен и обратный переход – от основной задачи ЛП к задаче с ограничениями-неравенствами. Если в первом случае число переменных увеличивается, то во втором оно будет уменьшаться.
10