рефераты конспекты курсовые дипломные лекции шпоры

Раздел Программирование
/
Является выпуклым многоугольником (или выпуклой многоугольной областью).

Реферат Курсовая Конспект

Выберите учебное заведение

Является выпуклым многоугольником (или выпуклой многоугольной областью).

Является выпуклым многоугольником (или выпуклой многоугольной областью). - раздел Программирование, Линейное программирование Каждое Из Неравенств В Соответствии С Теоремой 1 Определяет Одну Из Полуплоск...

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

Пример: Построить множество решений системы неравенств

-5х1 + 4х2 <= 20 (I)

2х1 + 3х2 <= 24 (II)

х1 - 3х2 <= 3 (III)

x1 >= 0 (IV)

0 <= x2 <= 6 (V, VI)

Координаты угловых точек – вершин многоугольника находятся как координаты точек пересечения соответствующих прямых. Например, точка D – пересечение прямых II и III, т.е. ее координаты являются решением системы

2х1 +3х2 <= 24 (II)

х1 - 3х2 <= 3 (III)

откуда Х1 = 9, Х2 = 2, т.е. D(9;2). Аналогично находятся координаты других угловых точек: О(0;0), А(0;5), В(4/5;6), С(3;6), Е(3;0).

При построении областей решений систем неравенств могут встретиться и другие случаи:

§ множество решений – выпуклая многоугольная область;

§ одна точка;

пустое множество, когда систем неравенств несовместима.

Теорему 2 можно обобщить на случай трех и более переменных.

Теорема 3. Множество всех допустимых решений совместной системы m линейных уравнений с n переменными при (m < n) является выпуклым многогранником (или выпуклой многогранной областью в n-мерном пространстве).

Доказывать не будем, проиллюстрируем теорему на примере:

2х1 + 3х2 + х3 = 12

х1 + х2 - х4 = 1

Построить непосредственно множество решений системы уравнений с n = 4 (n >3) переменными нельзя. В данном случае (когда разность между числом переменных и уравнений n – m = 2) можно поступить так: разбить все переменные на основные, например х3 и х4 (определитель из коэффициентов при них отличен от нуля = 1 *(- 1) – 0 * 0 = -1), и неосновные (свободные) переменные х1 и х2, и вместо множества решений системы уравнений построить множество значений их неосновных переменных (это выполнить возможно, т.к. неосновных переменных всего две).

С этой целью выразим основные переменные через неосновные:

х3 = 12 – 2х1 – 3х2

х4 = -1 + х1 + х2

В(0;4)

Так как рассматриваются допустимые значения переменных, т.е. х1, х2, х3, х4 >= 0, то

III

12 – 2х1 – 3х2 >=0 (I)

-1 + х1 + х2 >=0 (II)

С(6;0)

А(0;1)

х1 >=0, х2 >=0 (III, IV)

D(1;0)

Решением полученной таким образом системы неравенств являются точки четырехугольника ABCD с четырьмя угловыми точками А(0;1), В(0;4), С(6;0), D(1;0).

В данном примере графические построения проведены не в пространстве всех переменных, а в плоскости двух неосновных переменных х1 и х2. Но так как любой паре неосновных переменных х1 и х2 соответствуют определенные значения основных переменных х3 и х4, а следовательно одно и только одно решение данной системы уравнений, то каждой точке построенного четырехугольника ABCD соответствует одна и только одна точка множества допустимых решений системы , представляющего в данном случае выпуклый многогранник в четырехмерном пространстве.

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

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

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

х1 и х2 (х3, х4 = 0) – недопустимое (т.к. х1 = -9, х2 = 10),

х1 и х3 (х2, х4 = 0) – допустимое Х1 = (1;0;10;0),

х1 и х4 (х2, х3 = 0) – допустимое Х2 = (6;0;0;5),

х2 и х3 (х1, х4 = 0) – допустимое Х3 = (0;1;9;0),

х2 и х4 (х1, х3 = 0) – допустимое Х4 = (0;4;0;3),

х3 и х4 (х1, х2 = 0) – недопустимое (т.к. х3 = 12, х4 = -1).

Из рисунка, иллюстрирующего решение, видно, что этим допустимым базисным решениям соответствуют угловые точки D(1;0), С(6;0), А(0;1) и В(0;4) четырехугольника ABCD.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Линейное программирование

А х а х a nxn b... при n является плоскостью а при n gt ее обобщением в n мерном...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Линейное программирование
Оптимизационная задача была сформулирована в общем виде: найти переменные х1, х2, …, хп, удовлетворяющие системе неравенств (уравнений) φi

Понятие экономико-математической модели
Существует много различных определений понятия «модель», отличающихся друг от друга. Но это понятие знакомо каждому: игрушечный корабль – модель корабля, фотоснимок пейзажа, географическая карта –

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

Задача о раскрое материалов.
На раскрой (распил, обработку) поступает материал одного образца в количестве А единиц. Требуется изготовить из него L разных комплектующих изделий в количествах, пропорциональных числам b1, b2, …

Система m линейных уравнений с n переменными
Система m линейных уравнений с n переменными имеет вид: а11*Х1 + а12*Х2 + …+ а1j*Xj + …+ а1n*Xn =

Геометрический смысл решений неравенств, уравнений и их систем
Теорема 1. Множество решений неравенства с двумя переменными а11х1 + а12х2 <= b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой а11х1 + а12х2 = b1, вкл

Свойства задач ЛП
Выше в лекции по ЛП было показано, что любая задача ЛП м.б. представлена в виде общей, канонической или стандартной задачи. Причем, от одной задачи можно перейти к другой. Будем рассматрив

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

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

Нахождение оптимума линейной функции
Пример: Решим симплексным методом задачу: F=2x1 + 3х2 à maxпри ограничениях: х1 + 3х2 &l

Особые случаи симплексного метода
Неединственность оптимального решения (альтернативный оптимум): Решим симплексным методом задачу: F=3x1 + 3х2 à max

Симплексные таблицы
Практические расчеты с использованием симплекс метода – на компьютере. Если вручную, то используются симплекс-таблицы. Будем решать задачу на максимум. I. После введения добавочных перемен