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 = γ.

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

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

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

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

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

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

объектом.


 

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

55810. КУЛЬТУРА КИЇВСЬКОЇ РУСІ КІНЦЯ Х – ПОЧАТКУ ХІ СТ 87.5 KB
  Мета: дати уявлення про розвиток писемності та рівень освіченості населення Київської Русі; ознайомити з найвизначнішими памятками цього періоду; охарактеризувати розвиток мистецтва...
55811. Київська Русь за Ярославичів 37.5 KB
  Мета: зясувати яким було становище держави за часів Ярославичів;чому точилася боротьба Ярославичів за Київський стіл чи перебувала Київська Русь на межі феодальної роздробленості визначити з якою метою збиралися зїзди князів та які рішення приймалися; розвивати логічне та історичне мислення школярів; виховувати в учнів інтерес до історії своєї держави. Очікувані результати: учні зможуть: характеризувати становище держави за часів Ярославичів пояснити причини боротьби князів за Київський стіл називати мету та рішення князівських...
55812. Княжа Русь-Україна в літописних оповіданнях 89.5 KB
  А чиїми літературноісторичними дорогами ми будемо мандрувати ви скажете нам самі розгадавши ключове слово нашого кросворду а допоможуть вам знання які ви здобули на уроках історії та української літератури з тем Княжа Русь Україна...
55813. Повторювально - узагальнюючий урок з теми «Княжа Русь-Україна» 46 KB
  Запитання Хто автор Повісті минулих літ Хто княжив у Києві до приходу Олега Хто прибив щит на воротах Константинополя З якої династії походив князь Ігор Назвіть імя князя який загинув від рук древлян. Який князь загинув у боротьбі з печенігами Хто і коли запровадив християнство на Русі Як називається перший збірник законів на Русі Хто його автор Хто і коли остаточно розгромив печенігів Як називався перший камяний храм Київської Русі Назвіть імя доньки князя Ярослава Мудрого яка стала королевою Франції....
55818. Українські рушники – обереги, символи працелюбності нашого народу 45 KB
  Ознайомити дітей з різними функціями рушника. Зал прикрашений різними рушниками. На стінах плакати: Хата без рушників родина без дітей Рушники на кілочку хата у віночку Не лінуйся дівонько вишивати буде чим гостей шанувати.