Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Найти минимальное значение линейной функции

Читайте также:
  1. C.3.2.3.2 Назначение
  2. C.5.4.2.1 Назначение
  3. C.7.4.2.1 Назначение
  4. C.7.5.2.2 Назначение
  5. D.1.3.1.3 Назначение
  6. D.2.3.1.3 Назначение
  7. DOS Fn 4fH: Найти следующий совпадающий файл
  8. DOS Fn 5eH: Разные сетевые функции
  9. E.1.2.2.1 Назначение
  10. E.2.2.2.1 Назначение
  11. F.13.4.2.1 Назначение
  12. F.2.2.2.1 Назначение



Геометрическая интерпретация задачи линейного программирования.

Рассмотрим задачу линейного программирования, система ограничений которой задана в виде неравенств.

Z = С1х12х2+... +СNxN (1.5)

при ограничениях

a11x1 + a22x2 + ... + a1NХN b1

 

a21x1 + a22x2 + ... + a2NХN b2

. . . . . . . . . . . . . . . . . . . . . . . . . . . (1.6)

aM1x1 + aM2x2 + ... + aMNХN bM

xj (j = 1, 2, ... ,n) (1.7)

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

Это все равно, что в системе (1.6) - (1.7) положить N=2. Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой ai1x1 + ai2x2 = bi ,(i = 1, 2, ..., m). Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы.

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

Если в системе ограничений (1.6) - (1.7) n = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого ai1x1 + ai2x2 + ai3x3 = bi ,(i = 1, 2, ..., n), а условия неотрицательности – полупространства с граничными плоскостями соответственно хj = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью. Пусть в системе ограничений (1.6) - (1.7) n 3; тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью ai1x1 + ai2x2 + aiNxN = bi (i = 1, 2, ..., m), а условия неотрицательности – полупространства с граничными гиперплоскостями хj = 0 (j = 1, 2, ..., n).

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

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







Дата добавления: 2014-01-15; Просмотров: 97; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.162.139.105
Генерация страницы за: 0.047 сек.