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

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

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

Рассмотрим задачу с ограничениями-равенствами. Такая задача является ОЗЛП. Дальше увидим, как от неравенств перейти к равенствам и наоборот.

Итак, формулировка основной задачи. Имеется ряд переменных x1, x2,…,xn. Требуется найти такие неотрицательные значения этих переменных, которые бы

удовлетворяли систему линейных уравнений следующего вида:

∑=1 = , i=̅̅̅̅̅1, , j=̅̅̅̅̅1, (**)

И, кроме того, обращали бы линейную функцию L в min. L=∑=1 → , xj-элементы решений. (*)

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

Любая совокупность решений xj≥ 0, = ̅̅̅̅̅1, , которая удовлетворяла условию (**),

называется допустимым решением основной задачи (ДРОЗ)

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

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

(**)

Рассмотрим вопрос о существовании оптимальных решений и по критерию минимизации ф-ии L находить:

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

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

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

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

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

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

2 1 + 2 − 3 + 4 = −1 { 1 − 2 = 2

1 − 2 3 = 3

матрица системы

.

расширенная матрица системы

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

∆2 = 5=∆1 =>rp=ri=3. r=3 система совместна

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

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

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

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

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

4. Геометрическая интерпретация ОЗЛП.

Информация из лекций

Геометрический способ решения используется если число неизвестных на 2 больше числа уравнений: n-m=2.

Дана система линейных уравнений:

1)Выбираем из линейных уравнений 2 свободных переменных (x1, x2),

остальные будут являться базисными (x3, x4, …, xn), их количество: m

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

3. Найдём в области координат свободных переменных x1 и x2 область допустимых решений, для которой все переменные, и свободные, и базисные будут неотрицательные: j = 1̅, n;̅ xj ≥ 0;

3.1. Приравниваем базовые переменные к 0, получаются уравнения прямых в координатах x1 и x2, по одну сторону от которых находятся области отрицательных значений, а по другую области положительных значений.

3.2. Наносим прямые на плоскость, выделяем области положительных значений. Совмещая области всех положительных значений, получаем область допустимых решений (выпуклый многоугольник).

Для нахождения оптимальных решений мы должны в этих координатах построить L и проанализировать положение L относительно ОДР.

Пример: m = 5

x1-x2+x3 = 4 2x1-x2-x3-x4 = -5 x1+x2-x5 = -4 x2+x6 = 5 2x1-2x2-x6+2x7 = 7

x1, x2 – свободные переменные x2 = x1-4

x2 = 1.5x1+0.5

x2 = -x1-4

x2 = 5

x2 = 2x-12

Алгоритм геометрического решения ЗЛП

1. Записать уравнения прямых, соответствующих ограничениям, и

построить их на плоскости х10х2.

2.Определить области, в которых выполняются ограничения задачи.

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

4.Определить направление возрастания (убывания) целевой функции f. Это можно сделать двумя способами.

Способ 1 Построить вектор-нормаль ̅n = (с1, с2), его направление показывает направление возрастания целевой функции f, в противоположном направлении функция f убывает.

Способ 2 Построить две линии уровня функции f: f=С1 и f=С2 (С1, С2 –произвольные константы) и по их расположению на плоскости х10х2 определить направление возрастания (убывания) функции.

5.Определить граничную точку или точки области допустимых решений, в которых целевая функция принимает максимальное (минимальное) значение. Для этого передвигаем нашу линию уровня f = С в направлении вектора n̅ (или в направлении возрастания целевой функции f) параллельно самой себе до тех пор, пока хотя бы одна ее точка будет принадлежать области допустимых решений.

6.Определить координаты найденной точки, решая систему уравнений, состоящую из уравнений прямых, на пересечении которых находится эта точка, или выявляя

уравнение граничной прямой области допустимых решений, с которой совпадает

линия уровня целевой функции.

Задача с двумя переменными

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

Пусть требуется найти максимальное значение функции: F = 2x1+3x2.

Задана система ограничений:

и х1 ≥ 0, x2 ≥ 0 — условия неотрицательности.

Будем считать, что данная задача описывает кирпичное производство: x1– количество кирпичей первого вида, x2 – количество кирпичей второго вида, выпускаемые по плану. За единицу измерения неизвестных выберем одну тысячу штук кирпича. Первым ресурсом пусть будет глина, её запас 10 т, второй ресурс – песок, запас – 6 т, третий ресурс − обжиговая печь,

мощность нашего предприятия оценивается в 3 единицы (одна единица равна 100 м3

обжиговой печи).

Рассмотрим экономический смысл остальных коэффициентов задачи: на производство одной тысячи кирпичей первого вида идёт 2 т глины, 2 т песка и 100 м3 – обжиговой печи; на производство одной тысячи кирпичей второго вида идёт 5 т глины, 1 т песка, 100 м3

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

(пусть будет 20 тыс. руб.) от реализации 1000 кирпичей первого вида, а от реализации 1000

кирпичей второго вида наша прибыль равна 30 тыс. руб. (за денежную единицу взяли 10 тыс.

руб.).

Построим область допустимых решений задачи (рисунок 1).

Рассмотрим уравнения прямых и воспользуемся для их построения формулой «Уравнение прямой в отрезках»: + = 1

L1: 2x1+5x2=10. Разделим уравнение на 10 Получим: 51 + 22 = 1

L2: 2x1+x2=6 Разделим уравнение на 6 Получим: 31 + 62 = 1

L3: x1+ x2=3. Разделим уравнение на 3 Получим: 31 + 32 = 1

Решением данной системы неравенств является заштрихованная область ОДР (область допустимых решений) – четырёхугольник OABC.

Рисунок 1

Теперь надо выбрать из всех возможных допустимых планов.

Для этого построим прямую, соответствующую целевой функции, и назовём её линией уровня 1: 2x1+3x2=0. Осталось выяснить, в какой точке найденной области функция достигает своего максимального значения.

Чтобы найти оптимальный план, достаточно «переходить» с одной линии уровня на другую в направлении возрастания целевой функции. Точка B окажется в данном случае критической точкой, через неё проходит прямая из семейства рассматриваемых параллельных прямых;

всякая точка любой прямой из того же семейства, проходящей «выше» точки B, доставляет целевой функции большее значение, однако всякая такая прямая не будет с ОДР иметь общих точек. А прямая, проходящая «ниже», в точке В пересекает область допустимых решений, но значение функции F будет на всех этих точках прямой меньше, чем значения F в точке B.

Вследствие этого точка B и есть оптимальный план, приносящий нам наибольшую прибыль.

Определим координаты точки B, то есть план, доставляющий максимальную прибыль,

оптимальный план. Поскольку эта точка есть пересечение первой и третьей прямых, то её координаты удовлетворяют уравнениям этих прямых: 2x1+5x2=10, x1+ x2=3 и находятся как решения системы уравнений

Имеем = (53 , 43).

Оптимальный план X0 = (53 , 43)

Таким образом, вычисление значения максимальной прибыли:

то есть выпуская кирпичи первого и второго видов, мы получим максимальную прибыль.

Ответ: 7,3 ден. ед., или 73 тыс. руб.

Различные случаи решения (единственный оптимальный план, оптимальных

планов бесконечное множество, оптимального плана нет)

В зависимости от вида ОДР и целевой функции F (рисунок 2) задача может иметь бесконечное множество 1), 2), одно решение 3), 4), не иметь ни одного оптимального решения 5), 6).

Рисунок 2

5.Задача ЛП с ограничениями-неравенствами. Переход от нее к основной задаче.

Пусть имеется задача ЛП с параметрами 1, 2 …

Ограничения имеют вид неравенств ≥ 0 , 0 ≤

Методом перестановки приводим к ≥ 0

Тогда ограничения могут принять такой вид:

11 1 + 12 2+. . . + 1 + 1 ≥ 0 { 21 1 + 22 2+. . . + 2 + 2 ≥ 0

. . .

1 1 + 2 2+. . . + + ≥ 0

Обозначим эту систему уравнений как (*)

Требуется найти такие неотрицательные значения 1, 2 … , которые удовлетворяют системе неравенств и обращают в минимум линейную функцию L.

[ = 1 1 + 2 2+. . . + ] →

Используется следующий прием:

Вводятся следующие переменные

они удовлетворяли системе линейных неравенств (**) и, кроме того, обращали бы функцию

→ .

В такой подстановке x1, x2 … xn – рассматриваются как свободные переменные. А переменные

1, 2 … – рассматриваются как базисные.

Перешли к классической подстановке.

Отличие:

Функция L сразу выражена через свободные переменные.