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

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

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

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

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

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

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

объектом.


 

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

48432. Історія сучасного світу. Опорний конспект лекцій 997.64 KB
  13 серпня 1961 року з метою перешкодження масовій втечі жителів НДР у Західну Німеччину. 9 листопада 1989 року новий уряд НДР оголосив про безперешкодний перехід зі Східного Берліна в Західний і навпаки. Офіційний демонтаж відбувся у січні 1990 року але частина стіни була залишена як памятка подій. Правовий статус Співдружності визначений Вестмінстерським статутом 1931 року який було уточнено в 1947 р.
48433. Операційний менеджмент. Опорний конспект лекцій 2.58 MB
  Мета викладання дисципліни формування у студентів навиків розробки та удосконалення операційної системи підприємства вмінь ефективного управління галузевими операційними підсистемами як основи забезпечення стратегічних цілей організації; комплексу знань щодо базових принципів основних категорій сучасних концепцій теоретичних положень та практичних методів управління основною діяльністю підприємства. В результаті вивчення дисципліни студент повинен усвідомити що операційна система є однією з найважливіших складових будьякого...
48434. Оценка и контроль персонала 118.9 KB
  Оценка персонала – процесс определения эффективности деятельности сотрудников в ходе реализации задач организации, позволяющий получить информацию для принятия дальнейших управленческих решений.
48435. РИТОРИКА ЯК НАУКА І НАВЧАЛЬНА ДИСЦИПЛІНА. ПРЕДМЕТ РИТОРИКИ, ЇЇ ОСНОВНІ ПОНЯТТЯ, ЗАКОНИ 30.68 KB
  ПРЕДМЕТ РИТОРИКИ ЇЇ ОСНОВНІ ПОНЯТТЯ ЗАКОНИ План: Визначення риторики як науки і навчальної дисципліни. Мета курсу красномовства предмет риторики. Модуси публічного виступу основні поняття риторики. Етапи розвитку риторики.
48437. Политология в системе наук об обществе 41.71 KB
  Обобщая различные характеристики можно констатировать что политика это деятельность в сфере отношений между большими социальными группами классами нациями государствами по поводу обретения организации использования политической власти и управления социальными процессами в интересах реализации их общественнозначимых запросов и потребностей. Из этого определения вытекает и структура политики основными компонентами которой являются: политический интерес представляющий собой внутренний осознанный источник политического поведения...
48438. Найдавніші часи. Початки людської цивілізації на території України 723.91 KB
  Початки людської цивілізації на території України Історія України це наука що вивчає розвиток людського суспільства на території України та його закономірності. Джерела вивчення історії України: усні міфи легенди казки народні пісні; писемні літописи документи щоденники мемуари; речові залишки жител знаряддя праці посуд одяг; антропологічні залишки людських поховань; мовні явища які відображають процес розвитку мови; етнографічні побут і звичаї народу; фоно й фотодокументи.На територію сучасної України люди прийшли...
48439. Учет основных средств 52.38 KB
  УЧЕТ СТОИМОСТИ ОСНОВНЫХ СРЕДСТВ Основные средства переносят свою стоимость на готовый продукт постепенно в течение длительного времени охватывающего несколько производственно-технологических циклов. Поэтому учет основных средств и отражение их в балансе организованы таким образом чтобы одновременно можно было показать сохранение ими первоначальной вещной формы и постепенную потерю стоимости. Следует различать первоначальную остаточную восстановительную стоимость основных средств. Первоначальная стоимость отражает фактические затраты на...