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

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

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

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

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

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

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

объектом.


 

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

74222. Фотоприемники. Оптроны 681 KB
  Оптроны В качестве фотоприемников могут использоваться различные вакуумные газоразрядные и полупроводниковые фотоэлектрические приборы у которых выходным параметром является изменяющийся во времени импеданс ZФD. Различают оптроны с внешней оптической и внутренней электрической связью с внешней электрической и внутренней оптической связью. Такие оптроны могут использоваться для преобразования электрических сигналов: усиления генерирования переключения формирования и т. В электронных схемах регенеративные оптроны могут выполнять функции...
74223. ПЛАНЕТА ЗЕМЛЯ: НЕТРАДИЦИОННАЯ МЕЖДУНАРОДНАЯ КООПЕРАЦИЯ И ЗАХОРОНЕНИЕ ЯДЕРНЫХ ОТХОДОВ Е.В. Комлева 278 KB
  Рассмотрены некоторые антропосоциальные аспекты феномена ядерной энергии, идея долговременной подземной изоляции ядерных материалов международными усилиями. Представлены российские версии. Отмечена необходимость разработки адекватных юридических, финансовых и экономических механизмов, социокультурных оснований и критериев реализации идеи
74224. Электронная эмиссия. Катоды 172.5 KB
  Катоды Электронная эмиссия – процесс испускания электронов каким либо телом. Распределение электронов по энергиям в металле подчиняется статистике Ферми Дирака. Согласно последней число электронов имеющих энергию в интервале от W до WdW будет...
74225. ЭЛЕКТРОННО-ИОННАЯ ПЛАЗМА 84.5 KB
  Развитие физики плазмы диктуется чисто практическими целями: новые источники энергии управляемый термоядерный синтез преобразователи непосредственно тепловой энергии в электрическую МГД – генераторы и т. Если возникает неравенство зарядов возникает поляризация плазмы следовательно возникает электрическое поле. Аналогично в течении малых промежутков времени возможно разделение зарядов – поляризация плазмы но масштаб этой поляризации обратно пропорционален времени существования.
74226. Приборы тлеющего разряда 397 KB
  Приборы дугового разряда с накаленным и холодным катодом. Использование газового разряда в приборах квантовой электроники. Особенности приборов тлеющего разряда Простейшие приборы – двухэлектродные.
74227. Светодиоды. Структуры. Материалы 571 KB
  Для генерации полезного излучения такой носитель практически потерян. С увеличением температуры наблюдается уменьшение ширины запрещенной зоны и как следствие увеличение длины волны излучения. При любом механизме рекомбинации длина волны излучения определяется соотношением...
74228. Свойства полупроводников 583 KB
  Дискретные моноэнергетические уровни атомов составляющие твердое тело расщепляются в энергетические зоны. Наибольшее значение для электронных свойств твердых тел имеют верхняя и следующая за ней разрешенные зоны энергий. И наконец если ширина запрещенной зоны Eg лежит в диапазоне...
74229. Концентрация электронов и дырок в собственном полупроводнике 753.5 KB
  Напомним что значком ni принято обозначать концентрацию собственных носителей заряда в зоне проводимости и в валентной зоне. концентрация собственных носителей определяется в основном температурой и шириной запрещенной зоны полупроводника...
74230. Р-п переход. Образование и зонная диаграмма р-n перехода 1.57 MB
  Образование и зонная диаграмма рn перехода Электронно-дырочным или pn переходом называют контакт двух полупроводников одного вида с различными типами проводимости электронным и дырочным. Классическим примером pn перехода являются: nSi – pSi nGe – pGe.8 приведены зонные диаграммы иллюстрирующие этапы формирования электронно-дырочного перехода...