Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Основные случаи графического решения задач линейного программирования
Случай двух переменных в экономике не имеет особого практического значения, однако его рассмотрение проясняет свойства задачи линейного программирования, делает геометрически наглядными способы решения и пути их практической реализации.
Пусть дана задача: Х = (х1; х2), max Z = c1x1 + c2x2, Дадим геометрическую интерпретацию этой задачи: а) построим плоскость Х1ОХ2. На этой плоскости каждое из линейных ограничений-неравенств задает некоторую полуплоскость. Полуплоскость – выпуклое множество, а пересечение выпуклых множеств – есть также выпуклое множество, значит область допустимых решений – есть выпуклое множество. При построении области допустимых решений (ОДР) возможны следующие ситуации (рис. 3 – 8).
б) перейдем к геометрической интерпретации целевой функции. Пусть ОДР – не пустое множество, например, многоугольник А1А2А3А4А5А6.(рис. 8). Выберем произвольное значение целевой функции: Z = Zо = > c1х1 + + с2х2 = Zо – это уравнение прямой линии (обычно берут Zо = 0), ее называют линией уровня целевой функции. Чтобы установить направление возрастания (убывания) целевой функции, найдем ее частные производные ; . Вектор = g ra d z – показывает направление наискорейшего возрастания целевой функции, вектор (- ) указывает направление наискорейшего убывания целевой функции, его называют антиградиентом. Вектор всегда перпендикулярен к линиям уровня Правило решения задачи линейного программирования: 1) строим область допустимых решений; 2) строим ; 3) проводим произвольную линию уровня Z = Zо (для контроля убеждаемся, что прямая z = zo ┴ ); 4) при решении задачи на mах перемещаем линию уровня Z = Zo параллельно самой себе в направлении вектора до тех пор пока она не коснулась области ДР в ее угловой точке (до т. А4), пока она не станет опорной. В случае решения задачи на min линию уровня Z = Zo перемещают в антиградиентном направлении (до т. А1); 5) определяем оптимальный план * = (х1*; х2*), то есть координаты угловой точки касания и экстремальное значение целевой функции Z*=Z(x* ).
Возможны следующие случаи: 1) оптимальный план единственный: опорная линия и ОДР имеют одну общую точку (этот случай уже рассмотрен);
5) задача не имеет решений, т. к. ОДР . Пример 4. Задача использования сырья: найти max Z = 50х1 + 40х2, если Решение. Обозначим Тогда: 1. Построим ОДР (рис. 12): для этого в системе координат Х1ОХ2 изобразим граничные прямые L1: 2x1 + 5x2 = 20, (0; 4) (10; 0); L2: 8x1 + 5х2 = 40, (0; 8) (5; 0) (ОДР – многоугольник АВСДО); L3: 5x1 + 6х2 = 30, (0; 5) (6; 0). 2. = (50; 40) => удобно строить не вектор , а l , где . Строим ,(5; 4). 3. Строим линию уровня: Z = 50x1 + 40x2 = 0 => x1 = – = – 0,8x2, (0, 0), (– 4, 5) и перемещаем ее в направлении . Эта прямая станет опорной в точке С. Функция Z принимает max значение в этой точке. Найдем точку С как точку пересечения прямых L2 и L3: = 48 – 25 = 23; = 240 – 150 = 90; = 240 – 200 = 40; оптимальный план: , Z max = 50 · 3,9 + 40 · 1,7 ≈ 260,3. Таким образом, чтобы получить max прибыль в размере 260,3 руб. надо запланировать производство 3,9 единиц продукции Р1 и 1,7 единиц продукции Р2. Пример 5. Задача составления рациона: найти min Z = 4х1 + 6х2 если Решение. 1. Строим ОДР Þ для этого в системе координат X1 ОХ2 изобразим граничные прямые (рис. 13):
4. Линия уровня станет опорной в точке В, найдем ее, решив систему: Þ Þ (·) В (2, 3). Оптимальный план (2,3) Þ Zmin = 4 ∙ 2 + 6 ∙ 3 = 26. Итак, чтобы обеспечить min затраты в день 26 руб. необходимо дневной рацион составить из 2 кг корма 1 и 3 кг корма 2. Замечание. С помощью графического метода может быть решена задача линейного программирования, система ограничений которой содержит m-линейно независимых уравнений и если n – m = 2.
Пример 6. Графическим методом найти оптимальный план задачи линейного программирования, при котором целевая функция Z = 2х1 – х2 + х3 – 3х4 + 4х5 достигает max значения при ограничениях: то есть n = 5, m = 3 и n – m = 2 Решение. 1. Решим систему методом полного исключения:
»
2. Подставляя эти значения в целевую функцию и в систему ограничений, получаем задачу линейного программирования с двумя переменными и и Z = 12 – 2x4 + 6x5 – 70 + 7x4 + 10x5 + 20 + 4x4 – 5x5 – 3x4 + 4x5 = – 38 + 6x4 + 15x5. Итак, найти max Z = – 38 + 6х4 + 15х5, если – 4x + 5x +x = 20 7x + 10x + x = 70 x – 3x + x = 6 x (j = 1, 2, 3, 4, 5). Отбрасывая в системе уравнений базисные переменные, приходим к системе неравенств: 3. Решаем полученную задачу графическим методом. а) Построим ОДР в плоскости Х4ОХ5 (рис. 14). Рис. 14 L1: – 4x4 + 5x5 = 20, (0; 4) (– 5; 0), L2: 7x4 + 10х5 = 70, (0; 7) (10; 0), L3: x4 – 3х5 = 6, (0; – 2) (6; 0); б) = (6; 15) Þ l = (2; 5), в) Zo = – 38 Þ 6x4 + 15x5 = 0, (0; 0) (5; – 2). г) Целевая функция принимает max значение в точке В, найдем ее Þ max Z = – 38 + 12 + 84 = 58. д) Для отыскания оптимального плана подставим значения х4 и х5 в x1, х2, х3, получим : х1 = ; х2 = 0; х3 = 0; х4 = 2; х5 = ; Ответ: = (; 0; 0; 2; ), max Z = 58.
Задания для самостоятельной работы Задание 1. Решите графическим методом задачу линейного программирования (x 1 ≥ 0, x 2 ≥ 0):
Задание 2. Найти графическим методом оптимальный план задач линейного программирования (х j ³ 0).
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2020-11-11; просмотров: 80; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.191.166.122 (0.067 с.) |