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

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

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

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

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

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

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

объектом.


 

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

40911. Вимірювання потужностей НВЧ 138.5 KB
  НВЧ Струмів майже немає Струми максимальні Подаємо НВЧ, тобто болометр перегрівається, баланс порушується. Для встановлення балансу опір збільшуємо так, щоб загальна потужність: . Для точності використовують . Інколи потрібно зменшити падаючу потужність. Для цього використовують атенюатори (поглинаюча пластина, що вставляється в хвилевід).
40912. Вимірювання довжини хвилі та частоти 91.5 KB
  Тому роблять так звані лінзові хвильоводи чим менше діелектрика тим менше втрати. Чим більша фокусна відстань тим більші втрати повязані з дифракцією. Втрати лінзового хвильоводу
40913. Генерування та підсилення НВЧ 107 KB
  Коефіцієнт підсилення підсилювача на тунельному діоді . При цьому тут вхід та вихід не розв’язані, тому, по суті, коефіцієнт підсилення є коефіцієнтом відбиття. Такі підсилювачі нестійкі, нестабільні – параметрично залежать від навантаження
40914. Параметричний підсилювач на НП-діодах 103.5 KB
  Останнім часом роблять малим, отже дуже велика, і її не використовують. Можна використовувати .Розглянемо телевізійний параметричний підсилювач. - позначені частоти відповідних резонаторів.
40915. Транзистори НВЧ 109 KB
  Ці транзистори є видозміненими звичайними транзисторами. Серійно випускають транзистори з . Використовують транзистори.
40916. Підсилювачі на НВЧ транзисторах 59.5 KB
  Аналогічно створюється резонанс та узгодження по опору на виході: Принципова схема підсилювача:Для узгодження з лінією 50 Ом підключають і трансформатор (лампу)підбирається так, щоб узгодити з опорам 50 Ом. Аналогічно створюється резонанс та узгодження по опору на виході:
40917. Невзаємні елементи НВЧ 98.5 KB
  Нехай маємо феромагнітне середовище в , при цьому орієнтація доменів , оскільки це енергетично вигідно. Нехай тепер , тобто додали невелике змінне поле у перпендикулярному напрямку. Звичайно, при цьому зміниться Тепер треба знайти , тобто . Розглядатимемо лінійну задачу, нелінійності не враховуємо.
40919. Плоскі хвилі в гіротропному середовищі 107.5 KB
  Тобто, у взаємодіючій хвилі довжина хвилі буде менша. Зсунемось від початку на період, тоді друга хвиля повернеться в початковий стан, а перша не встигне. Тоді дасть вектор під кутом до нульової площини. - кут Фарадея (кут повороту площини поляризації). , ми розглянули . Цей кут змінюється в залежності від відстані.