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

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

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

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

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

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

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

объектом.


 

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

65087. УКЕК В КУЛЬТУРНОМ ПРОСТРАНСТВЕ НИЖНЕГО ПОВОЛЖЬЯ 60 KB
  На южной окраине Саратова находятся остатки золотоордынского города Укека возникшего в конце 40 начале 50х гг. И в настоящее время города в отдельных регионах имеют значительные особенности. Многие считают что города у кочевников возникали сначала искусственно как военно-административные центры...
65088. Никудерийская орда как фактор чагатайской истории (1270-1330-е гг.) 99.5 KB
  Никудер поддержал Чагатаида Боракхана потерпел неудачу и попал под стражу. когда Боракхан опираясь на решение курултая в Таласе заявил о претензиях на южные территории входившие по завещанию Чингизхана в улус Чагатая.
65090. Караунасы-никудерийцы и их роль в чагатайской истории 63.5 KB
  Никудерийцы и Дувахан Согласно завещанию Чингизхана улус его сына Чагатая распространялся от уйгурских земель на востоке до Амударьи на западе а на юге имел пределом индийские владения. После поражения Боракхана и подчинения ильханами дома...
65091. Клад серебряных монет первой четверти XV в. из Туркмении 88 KB
  Осенью 1997 г. в Москву были привезены для продажи коллекционерам 350 серебряных монет из большого клада, найденного незадолго до того в северной части Туркменистана. Владелец А.Алиев сообщил, что точное место находки ему неизвестно...
65093. ХУДОЖЕСТВЕННОЕ ОФОРМЛЕНИЕ МУСУЛЬМАНСКИХ МОНЕТ: НАРУШЕНИЕ ЗАПРЕТА? 137.5 KB
  Но если монеты античной Греции Рима эллинистического Востока обычно ассоциируются с прекрасными портретами конными экипажами образами богов и богинь то традиционно оформленные дирхемы и динары Арабского халифата а после его распада монеты многих его идеологических преемников...