Множество решений системы линейных неравенств.

Свяжем с каждой точкой (x₁,x₂,…x_n) n-мерного пространства Rⁿ n-мерный вектор x=(x₁,x₂,…x_n) с началом в начале координат и концом в точке (x₁,x₂,…x_n). Множество векторов х=(х₁,х₂,...х_n) в Rⁿ, компоненты которых удовлетворяют m линейным неравенствам:

a₁₁х₁+a₁₂х₂+...+a_1nx_n ≤ b₁

a₂₁х₁+a₂₂х₂+...+a_2nx_n ≤ b₂

. . . . . . . . . . . . (2)

a_m1х₁+a_m2х₂+...+a_mnx_n ≤ b_m

называется множеством решений системы линейных неравенств.

В определении все неравенства записаны со знаком ≤. Умножая на

(-1) любое из неравенств, можно изменить его знак на противоположный. Множество решений определено для систем линейных неравенств как со знаком ³ так и ≤.

Вопросы моделирования

Предмет теории моделирования

Моделирование - это замещение одного объекта (оригинала) другим (моделью) и фиксация и изучение свойств модели. Замещение производится с целью упрощения, удешевления, ускорения изучения свойств оригинала.

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

Множество параметров и их значений отражает ее внутреннее содержание- структуру и принципы функционирования. Характеристики -это в основном ее внешний признаки, которые важны при взаимодействии с другими .

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

Теория моделирования - взаимосвязанная совокупность положений, определений, методов и средств создания моделей. Сами модели являются предметом теории моделирования.

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

Роль и место моделирования в исследовании систем.

Познание любой системы ( ) сводится по существу к созданию ее модели. Перед изготовлением каждого устройства или сооружения разрабатывается его модель- проект. Любое произведение искусства является моделью, фиксирующее действительность.

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

Классификация моделей

Физические модели. В основу классификации положена степень абстрагирования модели от оригинала. Предварительно все модели можно подразделить на 2 группы - физические и абстрактные ( математические).

Ф.М. обычно называют систему, эквивалентную или подобную оригиналу, но возможно имеющую другую физическую природу. Виды Ф.М.:

- натуральные;

- квазинатуральные;

- масштабные;

- аналоговые;

Натуральные модели - это реальные исследуемые системы ( макеты, опытные образцы). Имеют полную адекватность ( соответствия) с системой оригинала, но дороги.

Квазинатуральные модели - совокупность натуральных и математических моделей. Этот вид используется тогда, когда модель части системы не может быть математической из-за сложности ее описания (модель человека оператора) или когда часть системы должна быть исследована во взаимодействии с другими частями, но их еще не существует или их включение очень дорого ( вычислительные полигоны, АСУ).

Масштабная модель - это система той же физической природы, что и оригинал, но отличается от него масштабами. Методологической основой масштабного моделирования является теория подобия. При проектировании ВС масштабные модели могут использоваться для анализа вариантов компоновочных решений.

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

Математические модели. Математические модели представляют собой формализованное представление системы с помощью абстрактного языка, с помощью математических соотношений, отражающих процесс функционирования системы. Для составления математической модели можно использовать любые математические средства - алгебраическое, дифференциальное, интегральное исчисления, теорию множеств, теорию алгоритмов и т.д. По существу вся математика создана для составления и исследования моделей объектов и процессов.

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

Аналитической моделью называется такое формализованное описание системы, которое позволяет решить уравнение в явном виде, используя известный математический аппарат.

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

Имитационная модель - это совокупность описания системы и внешних воздействий, алгоритмов функционирования системы или правил изменения состояния системы под влиянием внешних и внутренних возмущений. Эти алгоритмы и правила не дают возможности использования имеющихся математических методов аналитического и численного решения, но позволяют имитировать процесс функционирования системы и производить вычисления интересующих характеристик. Имитационные модели могут быть созданы для гораздо более широкого класса объектов и процессов, чем аналитические и численные. Поскольку для реализации имитационных моделей служат ВС, средствами формализованного описания им служат универсальные и специальные алгоритмические языки. Им в наибольшей степени подходят для исследования ВС на системном уровне.

Рассмотрим ряд задач, в которых необходимо найти область решения системы линейных неравенств.

Пример 1: Изобразить множество решений следующей системы линейных неравенств в R².

x₁ + 3х₂ ≤ 6

х₁ - х₂ ≤ 2

х₁ ³ 0

Решение

рис.2

Искомое множество решений соответствует заштрихованной области. Вершинами множества решений служат три точки (0,2), (0,-2) и (3,1). Ониявляются точками пересечения прямых, ограничивающих множество решений.

В этом примере множество решений - многогранное выпуклое множество.

Пример 2: Изобразить множество решений следующей системы линейных неравенств в R².

-x₁ + 2х₂ ≤ 4

3х₁ + 2х₂ ≤ 6

х₁ ³ 0

Решение

рис.3

Вершинами искомого множества являются две точки с координатами: (0,2) и (1/2, 9/4). Точка с координатой (0,3) вершиной не является, так как не удовлетворяет первому неравенству. Это множество решений - неограниченно.

РешениеПример 3:Изобразить множество решений следующей системы линейных неравенств в R².

х₁ - х₂ ³ 1

х₁ + х₂ ≤ 1

х₂ ³ 2

рис.4

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

Основная задача линейного программирования.

В общем виде задача линейного программирования (ЗЛП) ставится следующим образом.

Найти вектор х=(х₁,х₂, ... x_n) в Rⁿ, который максимизирует (или минимизирует) целевую функцию

F(x)=с₁х₁+с₂x₂ +... +с_nx_n (3)

и удовлетворяет m+n линейным неравенствам:

a₁₁х₁+a₁₂x₂+...+a_1nx_n ≤ b₁

a₂₁x₁+a₂₂x₂+...+a_2nx_n ≤ b₂

. . . . . . . . . . . . (4)

a_m1x₁+a_m2x₂+...+a_mnx_n ≤ b_m

x₁³0, x₂³0, ... x_n³0

В терминологии программирования линейная функция F(х) называется целевой функцией задачи. Множество решений системы линейных неравенств (4) называют множеством допустимых решений, а любой вектор х из этого множества называется допустимым решением. Оптимальным решением называется вектор х*, при котором целевая функция принимает своё максимальное (или минимальное) значение на допустимом множестве решений.

Графический метод решения задач линейного программирования. Покажем, как решается указанная задача графическим (геометрическим) методом. Для этого ограничимся рассмотрением системы линейных неравенств с двумя неизвестными.

Пусть задана целевая функция F=с₁х₁+с₂х₂+с₀. Найдём среди множества точек (х₁,х₂) из области допустимых решений совместной системы неравенств (4) (содержащей только переменные x₁ и x₂) такие, которые придают линейной функции F наименьшее (наибольшее) значения. Для каждой i – ой точки плоскости функция F принимает фиксированное значение F=F_i. Множество всех таких точек на которых функция F принимает одно и то же значение F_i есть прямая с₁х₁+c₂х₂+c₀=F_i = const, перпендикулярная к некоторому вектору, называемому градиентом F (grad F). Этот вектор выходит из начала координат и имеет координаты grad F =(с₁,с₂). По свойству вектора grad F если указанную прямую передвигать параллельно самой себе в положительном направлении вектора grad F, то значение целевой функции F=с₁х₁+с₂х₂+с₀ на этой прямой будет возрастать, а в противоположном направлении - убывать.

Пусть при движении прямой F=const в положительном направлении вектора grad F эта прямая впервые встретится с многоугольником допустимых решений в его вершине. Тогда в этом положении F₁ прямая F=const называется опорной, и на этой прямой функция F принимает наименьшее значение. При дальнейшем движении в том же направлении (положительном) прямая F=const пройдёт через другую вершину многоугольника допустимых решений и выходя из области решений также станет опорной прямой F₂. На ней функция F принимает наибольшее значение среди всех значений, принимаемых на многоугольнике допустимых решений. Таким образом, минимизация и максимизация целевой функции F=с₁х₁+с₂х₂+с₀ на многоугольнике допустимых решений достигается в точках пересечения этого многоугольника с опорными прямыми F=с₁х₁+с₂х₂+с₀ = const, нормальными к вектору grad F=(с₁, с₂). Это пересечение опорной прямой с множеством допустимых решений может быть либо в одной точке (вершине многоугольника), либо в бесконечном множестве точек (если это множество сторона многоугольника).

Задание по первой, второй, третьей задаче выбирается по фамилии имени отчеству студента, а по четвертой задаче выбирается по фамилии и отчеству.

Задача №1

Таблица 1

Пример 4: Минимизировать линейную форму F=14x₁+4x₂ при ограничениях:

7х₁+ 2х₂ ³ 14

-х₁ + х₂ 2

4 х₁ –7x₂ ≤ 14

8x₁+ 9x₂ 72

x₁ 0, x₂ 0.

Решение.

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

7х₁+2х₂ =14

-х₁+х₂ =2

4 х₁ – 7x₂ = 14

8x₁+9x₂=72

x₁=0, x₂ =0.

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

рис 5.

Для нахождения точек экстремума построим прямую F=14x₁+4x₂=0 и вектор gradF = (14, 4). Будем передвигать прямую F=0 параллельно самой себе в направлении вектора grad F. С многоугольником ABCDE эта прямая впервые встретиться в точках Е(2,0) и А(10/9, 28/9), где целевая функция принимает одно и то же минимальное значение F(E) = F(A) =14·2+4∙0=28-min, (т.к. вектор grad F перпендикулярен прямой АЕ). Таким образом, минимальное значение целевая функция принимает в любой точке отрезка AE.

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

Опорный план называется невырожденным, если он содержит ровно положительных компонент; в противном случае план является вырожденным.

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

Базисным решением системы m линейных уравнений с переменными называется всякое ее решение, в котором все не основные переменные имеют нулевые значения.

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

Теорема 2. Если задача линейного программирования имеет оптимальное решение, то оно совпадает с угловой точкой множества допустимых решений.

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

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

Понятие о симплекс-методе.

Теорема 1. Если ЗЛП имеет оптимальное решение, то целевая функция принимает экстремальное значение в одной из угловых точек выпуклого многоугольника допустимых решений.

Теорема 2. Каждому опорному решению ЗЛП соответствует угловая точка многоугольника допустимых решений и наоборот.

Исходя из этих теорем, при реализации симплекс-метода осуществляется целенаправленный перебор всех вершин так, чтобы в каждой следующей вершине значение целевой функции было бы не меньше (не больше) чем в предыдущей вершине. При этом за конечное число шагов достигается искомое оптимальное решение, или устанавливается, что ЗЛП неразрешима.

Для осуществления указанного алгоритма выберем в системе (5) max набор линейно независимых переменных (тех, для которых определитель составленный из коэффициентов перед этими переменными отличен от 0). Пусть для определенности это будут переменные х₁, х₂,... х_r (r ≤ m). Выразим эти переменные через остальные переменные

х₁ = а'_1,r+1 х_г+1 + ... + a'_1n х_n + b₁'

х₂ = а'_2,r+1 х_г+1 + ... + a'_2n х _n + b₂' (6)

. . . . . . . . . . . . . . . .

х_r = a'_{r, r+1} х_г+1 + ... + a' _{r n} x_n + b_r'

причем будем предполагать, что все b₁'³0, b₂'³0, b_r'³0. Если исходные ограничительные условия заданы неравенствами, то их можно преобразовать к виду (5) путём введения новых неотрицательных переменных, так называемых балансовых (выравнивающих). Так, например,в неравенствеа₁х₁+а₂х₂+…+а_nх_n ≤ b достаточно добавить к левой части неравенства некоторую величину х_n+1 ³ 0 равную разности между правой и левой частями неравенства и мы получим равенство a₁x₁ + а₂х₂+…+а_nх_n + x_n+1 = b. Если ограничительные условия заданы смешанным образом, то есть неравенствами и уравнениями, тогда указанным путём их так же можно свести только к уравнениям.

В полученной системе (6) переменные (неизвестные) х₁,х₂ ... х_г называются базисными, а весь набор {х₁, х₂ ... х_г} - базисом, ос­тальные переменные называются свободными. Система ограничений (6) называется системой, приведённой к единичному базису. Подставляя в целевую функцию F вместо базисных переменных их выражения через свободные из системы (6) получим

F = C₀ + C_г+1 х_г+1 + … + C_nх_n

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

х₁=b₁' , х₂= b₂' , ... x_r=b_r'

Полученное таким образом допустимое решение системы (6)

(b₁' ,b₂' , ... b_r' , 0, ... 0) называется базисным. Для этого базисного решения значение целевой функции будет равно F_Б= C_0.

Решение задачи при помощи симплекс-метода распадается на ряд шагов, заключающихся в том, что от данного базиса Б мы переходим к другому базису Б' с таким расчётом, чтобы значение F_Б на новом базисе увеличивалось или, по крайней мере, не уменьшалось, то есть выполнялось F_Б' ≥ F_Б. При этом если все b₁'>0, b₂'>0,…., b_r'>0 , то данное решение называется опорным и соответствует какой-нибудь угловой точке области допустимых решений определяемой исходной системой ограничений. Тогда переход от одного базисного (опорного) решения к другому соответствует переходу от одной вершины многоугольника допустимых решений к другой вершине.

ЗАДАЧА№2

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами органических материально-денежных ресурсов в количестве , , единиц. При этом для продажи 1 группы товаров на 1 тыс.руб. товарооборота расход утерся в количестве единиц, ресурса второго вида в количестве единиц, ресурса третьего вида в количестве единиц. Для продажи 2 и 3 групп товара на 1 тыс.руб. товарооборота расходуется соответственно ресурса первого вида в количестве , единиц, ресурсов второго вида в количестве , единиц, ресурсов третьего вида в количестве , единиц. Прибыль от одах трех групп товаров на 1тыс.руб. товарооборота составляет соответственно , , (тыс.руб.).

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

Первая буква

Фамилия

Имя

Отчество

А

Б

В

1 0

Г

Д

Е

Ж

З

И

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш Э

Ю Я

Пример 5: Максимизировать целевую функцию F=-х₄+х₅ при ограничениях:

Решение.

Данная система уравнений совместна, так как ранги матрицы системы

и расширенной матрицы

совпадают и равны 3. Выражая базисные переменные (стоящие в единичных столбцах) х₁, х₂, х₃, через свободные переменные х₄ и х₅, приходим к системе

(7)

Помимо системы (7) базисные переменные выразим через свободные переменные и в целевой функции (в нашем примере F = -x₄ + x₅ уже выражена через свободные переменные x₄ и x₅). Полагая теперь х₄ = 0, х₅=0 находим базисные переменные: х₁=1, х₂=2, х₃=3. Таким образом, первое допустимое базисное решение системы уравнений есть (1, 2, 3, 0, 0) . При найденном допустимом решении целевая функция F имеет значение 0, то есть F₁=0.

Теперь попытаемся увеличить значение F₁. Увеличение х₄ уменьшит F₁, так как перед х₄ в выражении F = -x₄ + x₅ стоит отрицательный коэффициент, а увеличение x₅ даёт увеличение F₁. Увеличим поэтому x₅ так, чтобы х₁, х₂, х₃, не стали отрицательными, оставив х₄=0. Из второго уравнения (7) видим, что х₅ можно увеличить до 2 (так, чтобы x₂оставалось бы 0, при x₄ = 0). Тогда значение переменных будут (5, 0, 1, 0, 2), а значение F₂ = 2. Как видно величина F на втором шаге увеличилась.

Поскольку x₂ и x₄ оказались равными 0, то далее примем за свободные неизвестные х₂ и х₄, тогда х₅ = 2-х₂+2х₄

и от системы (7) переходим к эквивалентной ей системе (8)

(8)

Причем и F в этом случае будет равной

F = 2-х₂+х₄

Для увеличения F будем увеличивать х₄ (так как перед x₂ стоитотрицательный коэффициент) Из второго уравнения системы (8) видно, что при условии неотрицательного х₃ значение х₄ можно довести до х₄=1/5, тогда имеем (28/5, 0, 0, 1/5, 12/5), F₃ =11/5.

Поскольку в решении получено x₂ = x₃ = 0, то примем x₂ и x₃ за свободные переменные и выразим х₁, х₄, х₅, через х₂ и х₃ .Получим

x₁ = 28/5 - 7/5 x₂ - 3/5 x₃

x₄ = 1/5 + 1/5 x₂ – 1/5 x₃

x₅ = 12/5 – 3/5 x₂ – 2/5 x₃

причем F = 11/5 – 4/5 x₂ – 1/5 x₃

Так как коэффициенты при x₂ и при x₃ в выражении для F отрицательны, то увеличить значение F уже невозможно. Поэтому полагая х₂= х₃=0 получаем наибольшее значение F = 11/5 при решении (28/5, 0, 0, 1/5, 12/5)

Ответ: F_max = 11/5 при X* = (28/5, 0, 0, 1/5, 12/5)

Симплексные таблицы.

Поскольку решать ЗЛП, используя такие рассуждения, как это делалось в предыдущем примере, явно неудобно для компактной записи решения, а так же для возможности программирования алгоритма решения на ЭВМ используются так называемые симплекс-таблицы. Для этого систему ограничений сведем к единичному базису

х₁ + а_1,r+1 х_г+1 + ... + a_1n х _n = b₁

х_i + а_i,r+1 х_г+1 + .... + a_{i n} х _n = b_i (9)

х_r + а_r,r+1 х_г+1 + ... + a_{r n} х _n = b_r

а целевую функцию F - к виду:

F = C_г+1 x_r+1 + ... + C_j х _j +…+ C_nx_n + C₀ (10)

Равенство (10) будем называть приведённым (к свободным переменным) выражением для функции F а коэффициенты C_j – оценками (индексами) соответствующих свободных переменных х_j.

Коэффициенты приведенной выше системы ограничений (9), а так же различные вспомогательные переменные заносятся в симплексную таблицу (Таблица 1)

Таблица 1

Базисные перемен-ные

Свободные члены

х1

...

хi

...

xr

хг+1

...

xj

...

хn

х1

b1

...

...

а1,r+1

...

a1j

...

a1n

...

...

...

...

...

...

...

...

...

...

...

хi

bi

...

...

аi,r+1

...

aij

...

ain

...

...

...

...

...

...

...

...

...

...

...

...

xr

br

...

...

аr,r+1

...

arj

...

arn

F=

C0

...

...

- Cг+1

...

- Cj

...

- Cn

Первые r столбцов с неизвестными x_i - это единичные столбцы при базисных переменных x₁,…,x_r . Следующие n-r столбцов – это столбцы при свободных переменных x_r+1,…,x_n. Полагая свободные переменные x_r+1 = …=

=x_n = 0, находим базисные переменные x₁ = b₁,…, x_r = b_r. При этом значение целевой функции F = C₀.

Найденный вектор-план X₁ = и значение целевой функции F = C₀ соответствуют некоторой вершине многоугольника допустимых решений. Переход к другой вершине и, следовательно, к другому вектор-плану и другому значению целевой функции осуществляется с помощью пересчета данной симплексной таблицы.

Не нашли, что искали? Воспользуйтесь поиском по сайту: