Материал: Материалы по курсу (часть 2)

На практике ограничения в задаче ЛП часто задаются не уравнениями, а неравенствами. Рассмотрим, как можно перейти от задачи с ограничениями-неравенствами к основной задаче ЛП.

Пусть имеется задача ЛП с n переменными в которой ограничения, наложенные на эти переменные, имеют вид линейных неравенств. В некоторых из них знак неравенства может быть  , в других  (второй вид сводится к первому переменой знака в обеих частях неравенства). Поэтому зададим все ограничения-неравенства в стандартной форме:

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

От задачи, поставленной таким образом, легко перейти к основной задаче ЛП. Введем обозначения:

;

;

,

Где – некоторые новые переменные, которые принято называть добавочными. Согласно условиям (1.4), эти добавочные переменные так же, как и , должны быть неотрицательными.

Таким образом, возникает задача линейного программирования в следующей постановке: найти такие неотрицательные значения n + m переменных ; чтобы они удовлетворяли системе уравнений (1.5) и одновременно обращали в минимум линейную функцию этих переменных

Рассмотрим работу станции скорой помощи. Известно, что имеется n классов больных (травматические, кардиологические, ожоговые и т. д.) Число вызовов (в день) по классу больных равно . На станции имеется m групп передвижных бригад скорой помощи (общего типа, кардиологические и т. д.) A1, A2 ,…, Am. Группа насчитывает бригад (и столько же машин). Выезд бригады из группы к больному класса обеспечивает эффективность обслуживания этого больного, равную . Предполагается, что каждая бригада может в день обслужить N вызовов. Кроме того, считается, что общее число выездов точно совпадает с числом вызовов, т. е.

или ,

где

Спрашивается, сколько вызовов от каждого типа больных должна об служить каждая группа этих бригад . чтобы суммарная эффективность обслуживания L, подсчитываемая по формуле , (1.6) была максимальна?

Это транспортная задача ЛП. Математически она формулируется как максимизация L (или минимизация L^   L) при ограничениях

, (1.7)

,

(1.8)

С целью достижения лучшего соответствия реальным условиям данная задача может быть усложнена, если равенства (1.7) и (1.8) заменить соответствующими неравенствами.

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

Оценка операции по нескольким показателям эффективности

S – стоимость лекарств

W – вероятность выздоровления пациента

W1, W2, Wk

Отбрасываем ненужные (большая стоимость или маленькая вероятность), далее решаем, что лучше.

• Исп. составных критериев

;

• + (взвешенная сумма)

• Сведение к одному показателю с некоторыми ограничениями, нахождение максимума первого показателя при ограничениях на оставшиеся

В рабочей области ab находится max значения

3. Основная задача линейного программирования (озлп). Допустимые решения и оптимальное решение задачи лп.

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

Рассмотрим задачу с ограничениями-равенствами. Такая задача является ОЗЛП.

Дальше увидим, как от неравенств перейти к равенствам и наоборот.

Итак, формулировка основной задачи. Имеется ряд переменных x₁, x₂,…,x_n.

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

, i=, j= (**)

И, кроме того, обращали бы линейную функцию L в min.

L=, xj-элементы решений. (*)

В некоторых задачах функция L может максимизироваться, но ее также можн привести к стандартному виду, поменяв знак у ф-ции L.

Любая совокупность решений xj, которая удовлетворяла условию (**), называется допустимым решением основной задачи (ДРОЗ)

То или те из допустимых решений ОЗ, которые удовлетворяют условию (*), то ест обращают в min функцию L, составляют оптимальное решение.

Рассмотрим вопрос о существовании допустимых решений.

(**)

Не имеет решений

В обл. отриц. значений ()

ДРОЗ

Одно решение

Открытая

В случае открытой обл. оптимальных решений может не быть

Рассмотрим более подробно вопрос о существовании допустимых решений. В линейной алгебре доказывается, что для совместимости системы линейных уравнений необходимо и достаточно, чтобы ранг матрицы системы Zc был равен рангу расширенной матрицы системы Zp. В этом случае системы линейных уравнений имеют решения.

Матрицей системы линейных уравнений называется таблица, составленная из коэффициентов при неизвестных , i=, j=

Расширенной матрицей системы линейных уравнений называется та же матрица, дополненная столбцом свободных членов:

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

Пример 1. Определить, являются ли совместными следующие системы линейных уравнений.

= 2*(-1)*(-2)+0+0-(-1)*(-1)*1-(-2)*1-0=5=>r_i=3

= 5==>r_p=r_i=3. r=3 система совместна

r_p=r_i=r система совместна и полученное значение является рангом линейных уравнений, показывает число независимых линейных уравнений r m, r n. В дальнейшем будем рассматривать только независимые уравнения=>r=m(1).r=n в этом случае система имеет 1 решение.

Если определитель матрицы i=, j=, не равен 0, то находим решения для каждого элемента решения j=

Для области линейного программирования этот вариант не уместен. Правда нужно отметить: если xj.

Для нас представляет интерес 2-й случай r=m, r <n (2) в этом случае, решая систему, мы находим целую область допустимых решений, т.е. множество значений для каждого неизвестно. В зависимости от того n-m=2, то используется геометрический способ решения. Если (n-m)>2, то используется вычислительные методы решения.

(n-m)свободные переменные. В области свободных переменных будем искать ОДР, остальные переменные назначаются базисными переменными. Они дают ограничения в области допустимых решений.