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

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

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

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

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

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

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

объектом.


 

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

14329. Визначення прискорення вільного падіння за допомогою математичного маятника 71 KB
  Лабораторна робота №2 Визначення прискорення вільного падіння за допомогою математичного маятника Мета роботи: Виміряти прискорення вільного падіння по періоду коливанняматематичного маятника; Визначити закони гармонічного коливального руху.
14330. Визначення модуля Юнга при згину стержня 69 KB
  Лабораторна робота №3 Визначення модуля Юнга при згину стержня Мета роботи. Визначити модуль пружності модуль Юнга для сталі при згині стержня. Прилади та обладнання. Установка для визначення модуля Юнга по стрілі прогину набір тягарців індикатор штангенцирк
14331. Визначення моменту інерції маятника Обербека 82.5 KB
  Лабораторна робота №4 Визначення моменту інерції маятника Обербека Мета роботи: Використовуючи основний закон динаміки обертового руху визначити момент інерції хрестоподібного маятника Обербека Прилади та обладнання: хрестоподібний маятник Оберб...
14332. Механіка матеріальної точки. Механіка твердого тіла 1.26 MB
  ФІЗИКА Методичні рекомендації Модуль І Механіка матеріальної точки€ Модуль ІІ Механіка твердого тіла€ В методичних рекомендаціях наведені типові задачі з рішенням а також приклади задач для самостійної роботи. Заг
14333. Механіка матеріальної точки та твердого тіла 5.29 MB
  ФІЗИКА Методичні рекомендації до вивчення курсу фізики. €œМеханіка€ модуль ІІІ. Для студентів спеціальностей: У методичних рекомендаціях викладено повний лекційний курс з дисципліни фізики з розділу €œМеханіка матеріальної точки та твердого тіла€ а також навед
14334. Механіка матеріальної точки. Механіка твердого тіла. Методичка 1.78 MB
  Методичні рекомендації до виконання лабораторних робіт з дисципліни ФІЗИКА Модуль 1 €œМеханіка матеріальної точки€ модуль 2 €œМеханіка твердого тіла€ Миколаїв – 2010 Методичні рекомендації до виконання лабораторних робіт з дисципліни фізика розділу Ме...
14335. Вимірювання фізичних величин та обробка результатів. Методичка 619.5 KB
  МЕТОДИЧНІ РЕКОМЕНДАЦІЇ ДО ЛАБОРАТОРНОГО ПРАКТИКУМУ З ФІЗИКИ €œВимірювання фізичних величин та обробка результатів€ для студентів спеціальностей Методичні рекомендації до лабораторного практикуму з фізики: €œВимірювання фізичних величин та обробка результа
14336. Оценка достоверности результатов эксперимента с помощью критерия Пирсона 242.5 KB
  Лабораторная работа №5 Тема: Оценка достоверности результатов эксперимента с помощью критерия Пирсона Цель работы: ознакомление и приобретение навыков статической обработки результатов экспериментальных данных в судостроении Задача: выполнить статическую обрабо...
14337. Якорное устройство судна. Экспериментальная оценка уравнения цепной линии 270.5 KB
  Тема: Якорное устройство судна. Экспериментальная оценка уравнения цепной линии. Цель работы: Ознакомление с характеристиками и физическим явлением используемом в якорном устройстве. Задача: Определить основные параметры формы тяжелой гибкой нити усилия натя...