Примеры решения задачи ЛП графическим методом

Рассмотрим несколько примеров.

Пример 1. Максимизировать линейную форму F = x1+ x2 при ограничениях:

Примеры решения задачи ЛП графическим методом - student2.ru

Построим прямые

x1 -2
x2
 
 

I: 3x1 – 2x2 = – 6

II: 3x1 + x2 = 3

x1
x2

III: x1 = 2

Примеры решения задачи ЛП графическим методом - student2.ru Примеры решения задачи ЛП графическим методом - student2.ru

Учитывая знаки неравенств, определим полуплоскости решений и, таким образом, область допустимых решений системы – четырехугольник MNPQ.

Построим Примеры решения задачи ЛП графическим методом - student2.ru Тогда линия уровня при выходе из четырехугольника решений пройдёт через точку N. Координаты точки N найдём как пересечение двух прямых I и III:

Примеры решения задачи ЛП графическим методом - student2.ru

Тогда линейная функция F принимает наибольшее значение в точке N, т.е. максимизируется

Примеры решения задачи ЛП графическим методом - student2.ru

Пример 2. Минимизировать функцию F = x1+ x2 при ограничениях:

Примеры решения задачи ЛП графическим методом - student2.ru

Построим прямые

x1
x2
 
 

I: x1 + x2 = 3

II: x1 + x2 = 7

x1
x2

III: x2 = 1

IV: x2 = 4

V: x1 = 4

Примеры решения задачи ЛП графическим методом - student2.ru

Область допустимого решения системы – многоугольник ABFMNP. Вектор Примеры решения задачи ЛП графическим методом - student2.ru Линия уровня, выходя из многоугольника решений в направлении, противоположном Примеры решения задачи ЛП графическим методом - student2.ru , пройдёт через точку B(0;4). Тогда

Примеры решения задачи ЛП графическим методом - student2.ru

Пример 3. Примеры решения задачи ЛП графическим методом - student2.ru

Примеры решения задачи ЛП графическим методом - student2.ru

Примеры решения задачи ЛП графическим методом - student2.ru

Полуплоскости, определяемые системой неравенств, не имеют общих точек. ОДР – пустое множество.

Таким образом, по причине несовместимости условий задачи, эта задача решения не имеет.

Пример решения экономической задачи графическим методом.

Пример. Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. В таблице 8 указаны наличный парк вагонов разных типов, из которых ежедневно можно комплектовать данные поезда, и количество пассажиров, вмещающихся в каждом из вагонов

Табл.8

Поезда Количество вагонов в поезде.
Багажный Почтовый Плацкартный Купейный Мягкий
Скорый
Пассажирский -
Число пассажиров - -
Парк вагонов

Определить оптимальное число поездов (скорых и пассажирских), обеспечивающее максимальное количество перевозимых пассажиров, при условии, что в день железная дорога не может пропустить более шести пассажирских поездов.

Построим математическую модель задачи. Целевая функция

Примеры решения задачи ЛП графическим методом - student2.ru

x1 – количество скорых поездов,

x2 – количество пассажирских поездов,

при условиях-ограничениях

Примеры решения задачи ЛП графическим методом - student2.ru

Построим вектор Примеры решения задачи ЛП графическим методом - student2.ru и ОДР:

x1
x2

I: x1 + x2 = 12,

 

II: x1=8,

III: 5x2 + 8x2 = 81,

x1 8,2
x2

IV: 6x1 + 4x2 = 70,

x1
x2

V: 3x2 + x2 = 26,

x1
x2

VI: x2 = 6

Примеры решения задачи ЛП графическим методом - student2.ru

Наибольшее значение целевая функция принимает в точке М, которая является пересечением двух прямых I и VI, найдём её координаты

Примеры решения задачи ЛП графическим методом - student2.ru

Примеры решения задачи ЛП графическим методом - student2.ru

Итак, максимальный пассажиропоток можно получить при данных условиях задачи, если будет сформировано оптимальное число поездов – 6 скоростных и 6 пассажирских.

Наши рекомендации