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

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

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

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

x1		-2
x2

I: 3x₁ – 2x₂ = – 6

II: 3x₁ + x₂ = 3

x1
x2

III: x₁ = 2

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

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

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

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

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

x1
x2

I: x₁ + x₂ = 3

II: x₁ + x₂ = 7

x1
x2

III: x₂ = 1

IV: x₂ = 4

V: x₁ = 4

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

Пример 3.

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

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

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

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

Табл.8

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

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

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

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

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

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

Построим вектор и ОДР:

x1
x2

I: x₁ + x₂ = 12,

II: x₁=8,

III: 5x₂ + 8x₂ = 81,

x1	8,2
x2

IV: 6x₁ + 4x₂ = 70,

x1
x2

V: 3x₂ + x₂ = 26,

x1
x2

VI: x₂ = 6

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

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