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

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

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

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

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

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

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

объектом.


 

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

23755. Набольший общий делитель 35.5 KB
  Основные цели: тренировать способность к практическому использованию алгоритма нахождения НОД на основе разложения чисел на простые множители; исследовать частные случаи нахождения НОД когда НОД а b = 1 НОД а b = а; сформировать понятие взаимно простых чисел; повторить и закрепить понятие смежных углов решение задач на одновременное движение примеров на порядок действий. – Здравствуйте ребята – Над какой темой мы с вами работали Нахождение НОД чисел методом разложения на простые множители. – Сегодня мы продолжим исследовать...
23756. Наибольший общий делитель 69.5 KB
  Основная цель: тренировать способность к нахождению НОД на основе разложения чисел на простые множители способность к рефлексии собственной деятельности; повторить и закрепить решение уравнений решение задач методом уравнений графическое изображение множеств с помощью диаграммы Венна. – Какой темой мы занимались на предыдущих уроках Нахождение НОД чисел методом разложения чисел на простые множители. – Чему равен НОД взаимно простых чисел НОД взаимно простых чисел равен 1. – Найдите: а НОД а b; б НОД b с; в НОД а с.
23757. Открытие нового знания 49.5 KB
  – Можно ли утверждать что числа a b и c кратны числу 14 a = b = c = Числа a и b кратны числу 14 т. в разложении этих чисел есть множители числа 14 а число с – нет т. в нём не содержится разложения числа 14. – Найдите частное от деления числа a на число 14 числа b на число 14.
23758. Открытие нового знания 38 KB
  – Здравствуйте ребята – Какая основная задача стояла перед нами на прошлых уроках Мы вывели новый способ нахождения НОК используя разложение чисел на простые множители. – Сегодня на уроке мы продолжим работать над нахождением НОК чисел и рассмотрим нахождение НОК разных чисел. – Найдите НОК 15 24: а составляя множества К 15 и К 24; б перебирая кратные 24; в с помощью разложения чисел 15 и 24 на простые множители.
23759. Наименьшее общее кратное 73 KB
  Основная цель: тренировать способность к нахождению НОК на основе разложения чисел на простые множители способность к рефлексии собственной деятельности; повторить и закрепить распределительное свойство умножения правило деления произведения на число действия с многозначными числами формулы объема и площади поверхности куба. – Чему мы научились на предыдущих уроках Мы учились находить НОД и НОК чисел разными способами. – Сегодня вы будете проверять на сколько хорошо вы усвоили метод нахождения НОД и НОК используя разложения чисел на...
23760. Признак делимости на 3 и на 9 48 KB
  Основные цели:– тренировать способность к доказательству общих утверждений на примере признаков делимости на 3 и на 9; повторить и закрепить изученные свойства и признаки делимости решение текстовых задач решение примеров на порядок действий построение формул зависимости между величинами. – Какие признаки делимости мы изучили Признаки делимости на 2 на 5 на 10 на 4 на 8 на 25. – А зачем нам нужны признаки делимости Что бы быстрее определять делится ли число на данное или нет.
23761. Признак делимости на 3 и на 9 57.5 KB
  – А зачем нам нужны признаки делимости Что бы быстрее определять делится ли число на данное или нет. Затруднения могут быть при выполнении задания тех случаях где множитель не делится ни на 3 ни на 9 или делится только на 3. 54 делится на 3 и третье т. 15 делится на 3.
23762. Признак делимости на 9 43 KB
  – А зачем нам нужны признаки делимости – Что бы быстрее определять делится ли число на данное или нет. Будет ли число представленное выражением d 235 делиться на5 – Всё зависит от того какое значение принимает d потому что если каждое слагаемое делится на 5 то и вся сумма разделится на 5 ели одно слагаемое делится на 5 а другое не делится на 5 то вся сумма не разделится на 5. 2 Будет ли число представленное выражением 271k делится на 2 –Всё зависит какое значение принимает k т. по свойству делимости произведения...
23763. Признаки делимости на 10, на 2, на 5 87.5 KB
  1 Выберите из множества A = числа кратные: а 2 б 5 в 10 г и 2 и 5 и 10. Кратные 2: 110; 300; 404; 706 т. П1 Кратные 5: 110; 215; 300 т. На доске: П2 Кратные 10: 110; 300 т.