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

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

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

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

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

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

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

объектом.


 

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

48233. Конспект лекцій з логіки 682 KB
  Відповідно до нормативних вимог Закону Про освіту і Болонського процесу курс лекцій з дисципліни âЛогікаâ включає в себе такі теми: предмет структура і призначення дисципліни поняття судження основні закони логіки умовивід логічні основи теорії аргументації доведення тести й самостійні завдання з логіки. Засвоївши курс âЛогікаâ студенти повинні: Знати: основний зміст усіх тем світоглядний потенціал законів логіки категорій особливості логічного...
48234. Конспект лекцій з релігієзнавства 492 KB
  Релігієзнавство являє собою комплекс суспільних наук, об'єктом вивчення котрих є релігія. Кожна з цих наукових дисциплін, виходячи з специфіки свого предмета, розглядає ту чи іншу сторону цього складного явища, що дозволяє в рамках релігієзнавства представити його цілісну картину
48235. Теорія соціальної роботи 141 KB
  Вступ до соціальної роботи: Підручник для студентів вищих навчальних закладів За ред. Вступ Зв'язки соціальної роботи з іншими дисциплінами мають взаємний характер. Адже здійснення соціальної допомоги передбачає попередній збір інформації її системний аналіз висування гіпотез побудову моделей розвитку.
48236. ЕКОНОМІЧНИЙ АНАЛІЗ (ТЕОРЕТИЧНІ ОСНОВИ) 802.03 KB
  Розглядаються теоретичні основи економічного аналізу, зокрема його значення та роль у системі управління підприємством, предмет та види економічного аналізу, його метод, методика факторного аналізу, характеристика способів детермінованого факторного аналізу, використання економіко-математичних методів в економічному аналізі, методика виявлення і розрахунку резервів, організація та інформаційне забезпечення аналітичних досліджень. Після кожної теми наведені контрольні питання для перевірки засвоєння матеріалу.
48237. ДВИГАТЕЛИ ВНУТРЕННЕГО СГОРАНИЯ 5.35 MB
  Остов двигателя Уравновешивание одноцилиндрового двигателя. Уравновешивание четырехцилиндрового однорядного двигателя Уравновешивание двухцилиндрового Vобразного двигателя.
48238. Л.Д. Малевич. Українська мова професійного спілкування 282.5 KB
  Стилі і норми української літературної мови в професійному спілкуванні Мовне законодавство в Україні Природа і функції мови. Місце української мови серед мов світу. Правовий статус української мови.
48239. УКРАЇНСЬКА МОВА ЗА ПРОФЕСІЙНИМ СПРЯМУВАННЯМ 888.5 KB
  Усне ділове спілкування. Етика ділового спілкування її предмет та завдання. Структура ділового спілкування. Мовленнєвий етикет Правила усного спілкування фахівця зустрічі переговори телефонне спілкування.
48240. ІСТОРІЯ УКРАЇНИ 430.5 KB
  Програма з курсу Історія України Укл. ВСТУПНЕ СЛОВО Пропоновані матеріали підготовлено з урахуванням проекту навчальної програми з курсу Історія України для вищих навчальних закладів освіти і передбачають розвязання таких завдань: а використання останніх досягнень світової і вітчизняної історичної науки в процесі викладання історії України; б постійне підвищення і вдосконалення наукового і виховного рівня викладання; в забезпечення реалізації в ході навчання принципів історизму та обєктивності в оцінці конкретних подій і явищ; г...
48241. УКРАЇНСЬКА КУЛЬТУРА 102.5 KB
  Ульяновський Українська наукова і культурницька еміграція у ЧехоСловаччині між двома світовими війнами Українська культура: розвиток ідеї та історія книги Автори Української культури: Дмитро Антонович Василь Біднов Дмитро Дорошенко Олександр Лотоцький Симон Наріжний Степан Сірополко Володимир Січинський Дмитро Чижевський Андрій Яковлів Українська культура: Лекції за редакцією Дмитра Антоновича Упор. Ця книжка унікальна спроба цілісного дослідження феномена української культури з найдавніших до...