19809

Геометричне розв’язання задачі лінійного програмування

Доклад

Информатика, кибернетика и программирование

Kак известно общая задача линейного программирования со стоит в поиске значений переменных удовлетворяющих некоторым линейным ограничениям и обеспечивающих наибольшее наимень шее значение заданной линейной функции. Например требование: максимизировать Lx1...

Украинкский

2013-07-17

16.74 KB

2 чел.

Kак известно, общая задача линейного программирования со-

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

линейным ограничениям и обеспечивающих наибольшее (наимень-

шее) значение заданной линейной функции. Например, требование:

максимизировать

L(x1, x2, x3) = 2x1 + x2 + 4x3

при условиях

x1 +2x2 + 3x3 12,

x1 0, x2 0, x3 0

означает пожелание не только отыскать значения неких величин x1,

x2 и x3, удовлетворяющих вышеприведенным четырем условиям, но и

среди них найти такие, что функция L(x1, x2, x3) принимает самое

большое значение.

В роли неизвестных величин могут выступать, например, объе-

мы выпуска продукции (обуви, приборов ночного видения или мик-

роскопов), распределение денежных средств на ликвидацию ветхого

жилья и строительство медицинских учреждений, тираж поэм М. Ю.

Лермонтова и «заговоров от сглаза»; ограничения связаны с расходом

материалов, наличием льгот на отдельные виды изданий, рыночной

конъюнктурой или личными предпочтениями, а целевая функция L(Х)

может определять прибыль от произведенной продукции или объем

неосвоенных средств.

Количество неизвестных величин, фигурирующих в постановке

задачи, называют ее размерностью. Набор их значений, удовлетво-

ряющих условиям задачи, называют планом (примером может слу-

жить программа производства – набор значений показателей, удовле-

творяющий ограничениям по сырьевым, социальным и прочим фак-

торам).

Может обнаружиться, что задача неразрешима – не существует

ни одного плана (ограничения противоречат друг другу). Может быть

единственный план или много (множество) планов, среди которых

надо найти наилучший (оптимальный), дающий максимум прибыли

2

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

затрат (жалоб населения, отходов при деревообработке и др.).

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

до нескольких сотен). Здесь мы намерены на примере двумерных за-

дач дать читателю наглядное, графическое представление о существе

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

рисовать на плоском листе бумаги и воспринимать конструкции ок-

ружающего нас трехмерного пространства). Наличие такого пред-

ставления может помочь и при обобщении выводов на задачи

бóльшей размерности.

Естественно, что для решения задачи желательно сначала полу-

чить представление о множестве планов (допустимых решениях) и

лишь затем из этого множества выбрать наилучший (с точки зрения

поставленной цели).

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

вестно, что уравнение αX + βY = γ на плоскости (X,Y) изображает

прямую линию (2x + 3y = 7, y = 0 или x – 2y = 0) и для ее построе-

ния достаточно взять пару подходящих точек. Неравенства же

αX + βY ≤ γ или αX + βY ≥ γ определяют полуплоскости, ограни-

ченные прямой αX + βY = γ.

Поскольку система ограничений двумерной задачи линейного

программирования определяет множество точек плоскости, лежащих

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

линиями, то множество планов может быть представлено точкой, ча-

стью прямой линии, фигурой, напоминающей выпуклый многоуголь-

ник, но никак не эллипсом, полумесяцем или другим криволинейным

объектом.


 

А также другие работы, которые могут Вас заинтересовать

73772. Початки української козачини 378 KB
  Вони брали ся за рішеннє сього питання тодї як се явище не тільки скристалїзувало ся вповнї набуло незвичайної екстензивної сили стало великою й впливовою суспільною верствою але й покрило собою иньші суспільні верстви стало репрезентантом української народности pr ехсеllеnсе подібно як народ шляхецькийrdquo; репрезентував сучасну народнїсть польську. І таке всенародне значіннє козачини в звязку з незмірноориґінальними прикладами козацького устрою козацької стихії що так різко відріжняли її на тлї загального поневолення народнїх...
73775. Профессионально-этические принципы работы практического психолога 25.21 KB
  Очевидные самоочевидные и даже в чемто банальные принципы типа не кричи на клиента не бей клиента не плюй в клиента не наноси ему увечий и т. Например психологконсультант неоправданно оскорбляет клиента доводя его до истерики или использует в некоторых случаях совершенно не адекватные методы был случай когда один весьма солидный специалист в профконсультации под видом инноваций применил метод иглоукалывания да еще в затемненной комнате при свечах и с полуобнаженным телом ошарашенного подростка. Роджерса пишет:...
73776. Этические проблемы в научной деятельности психолога 22.64 KB
  Проблема в том что для чистоты исследования часто приходится работать в режиме субъектобъектных отношений что предполагает повышенную этическую готовность и нравственную ответственность психологаисследователя. Проблема недобросовестности исследования. Этическая проблема заключается в вынужденной необходимости истинных авторов соглашаться на такое соавторство ради того чтобы книга вообще была издана. Очень непростой является проблема семейственности в науке когда с одной стороны создаются благоприятные условия для откровенных...
73777. Важнейшие требования к личности практического психолога 14.66 KB
  Иными словами превалирующая роль отводится психологическому и психотерапевтическому а также психокоррекционному и психодиагностическому инструментарию при этом личностные характеристики психолога считаются чемто вторичным. Подобная позиция присуща теоретическим концепциям рассматривающим психологическую помощь как воздействие психолога на клиента. Обобщая многочисленные исследования профессионально важных личностных черт психотерапевтов и психологов можно выделить следующие личностные черты желательные для практического психолога: ...
73778. Проблема «модели специалиста» и индивидуального стиля деятельности психолога 22.45 KB
  Обычно приводится примерно такое обоснование: невозможно втиснуть в модель все характеристики профессиональной деятельности вместе с необходимостью импровизировать в труде а также невозможно выделить общепризнанный стандартнообразцовый профиль личностных и профессиональных качеств специалиста под который можно было бы подгонять будущих психологов. Маркова выделяет следующие основные составляющие модели специалиста: 1 профессиограмму то есть описание самой деятельности психолога; 2 профессиональнодолжностные требования...
73779. Профессиональные деструкции в развитии психолога 22.97 KB
  Работа может способствовать личностному развитию но может иметь и отрицательные для личности последствия. Проблема в балансе соотношении позитивных и негативных изменений личности работника. Профессиональные деструкции проявляются в снижении эффективности труда в ухудшении взаимоотношений с окружающими в ухудшении здоровья и главное в формировании отрицательных личностных качеств и даже в распаде целостной личности работника. Специалисты обычно выделяют и анализируют негативные качества формирующиеся в работе школьных учителей: ...
73780. Эффективность труда психолога 20.5 KB
  Сложность оценки эффективности труда психолога связана с тем что основной результат его работы существует сокрыт во внутреннем мире других людей. Центральные вопросы связанные с оценкой эффективности деятельности профессионального психолога состоят в следующем: кто и по каким критериям может и должен производить эту оценку По всей видимости официально оценивать эффективность работы психолога должны четыре типа лиц или общественных групп: администрация организации где психолог работает профессиональное сообщество клиенты сам...