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

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

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

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

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

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

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

объектом.


 

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

30021. «Богатырь русского леса. Шишкин И.И.» (мультимедиа программа) 995 KB
  Картина №1. Афонасовский как прозывается он в наших краях под Елабугой Картина эта имела успех у публики. А для меня эта картина стала первой где многолетние свои наблюдения природы пытался я претворить в единый образ русского леса образ родины. Картина №2.
30023. Практические рекомендации по развитию интернет коммуникаций Фонда венчурных инвестиций ЧР www.e-birzha.cap.ru 1.39 MB
  Специфика корпоративного сайта как PRинструмента. Анализ официального сайта Фонда венчурных инвестиций ЧР www. История создания и ключевые требования к содержанию сайта. Анализ существующего состояния сайта www.
30024. Опытно - экспериментальная работа по формированию умений письма и письменной речи по средствам информационно – коммуникационных технологий 121.3 KB
  Информационнокоммуникационные технологии заняли прочное место в процессе обучения иностранному языку. Практика показывает что информационнокоммуникационные технологии имеют немало преимуществ перед традиционными методами обучения. Среди них можно выделить интенсификацию самостоятельной работы учащихся повышение познавательной активности и индивидуализацию обучения.
30025. Моделирование стрижек 61.22 KB
  Стрижка волос довольно сложная и серьезная операция которая требует предельного внимания и собранности. Укладка Волос это изменение структуры волоса на непродолжительное время чаще всего от мытья до мытья. В моде светлый цвет волос.
30026. Экспертиза эффективности и финансовой реализуемости инвестиционного проекта 635.15 KB
  Главным критерием оценки деятельности интерната для детейсирот является социальный эффект. В данном случае строительство интерната для детейсирот на территории Орловского района создаст рабочих мест. Для оценки эффективности предложенного в дипломе инвестиционного проекта проведем анализ положения детейсирот в Орловской области По информации Департамента образования молодежной политики и спорта в Орловской области по состоянию на 1 сентября 2012 года насчитывалось 2775 детейсирот и детей оставшихся без попечения родителей. В...
30027. Підприємство як суб’єкт господарювання в ринкових умовах 474.21 KB
  Базою для підприємства є діяльність як ініціативна самостійна так і систематична по виробництву продукції також надання послуг і зайнятість торгівлі що має за мету сприяти прибутку. Метод господарювання можна розкрити функціями що і визначають суть підприємства такі як: ресурсна організаційна та творча. Генеральну мету підприємства тобто чітко окреслену причину його існування у світовій економіці заведено називати місією. Здебільшого місією сучасного підприємства вважають виробництво продукції для задоволення потреб ринку та...
30028. Перспективы развития железнодорожного транспорта и путевого хозяйства 192.05 KB
  Владимир Иванович Якунин Президент ОАО РЖД Обеспечение перевозок безопасность пассажиров и сохранность перевозимых на железнодорожном транспорте грузов гарантируется единым производственнотехнологическим комплексом с вертикальной системой управления охватывающим 17 железных дорог 64 отделения дорог около 6000 железнодорожных станций 400 дистанций пути 220 локомотивных и 200 вагонных депо 200 дистанций...