Графический метод решения задач линейного программирования

Графический метод решения задач линейного программирования.

Автор:

Кулакова Кристина Рафаиловна

Учитель математики

МБОУ ОСОШ №11

Воронеж 2018 год

Графический метод решения задач линейного программирования.

Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида:

задача в которой фигурируют ограничения в форме неравенств, называется — основной (стандартной) задачей линейного программирования

,

.

Задача линейного программирования будет иметь канонический вид, если в общей задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства:

,

Основную задачу можно свести к канонической путём введения дополнительных переменных.

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

Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты с обратным знаком.

Пусть задача линейного программирования задана в двумерном пространстве, то есть ограничения содержат две переменные.

Найти минимальное значение функции

при ограничениях вида

и

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

Линейная функция (1) при фиксированных значениях является уравнением прямой линии , а вектор указывает направление возрастания целевой функции.

Далее рассмотрим примеры.

№1.

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

Определить оптимальное число скорых и пассажирских поездов, при котором число перевозимых пассажиров достигнет максимума.

Решение:

Пусть - число скорых, а - число пассажирских поездов.

Составим целевую функцию из соображений, что число перевозимых пассажиров должно быть максимальным.

Целевая функция будет иметь вид .

Используя данные из таблицы, составим систему неравенств-ограничений, которым должно удовлетворять решение задачи. Система имеет вид:

(4)

Так как в задаче всего 2 переменных, то удобно применять графический подход. В системе координат изобразим решение системы неравенств (4) и выделим многоугольник решений.

1)

2) 3)- оси координат.

3)

ОABC - многоугольник решений.

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

Точка В – точка выхода, ее координаты являются решением задачи. Найдем координаты точки, решив систему:

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

Ответ: число скорых поездов 6, число пассажирских поездов – 5, максимальное число пассажиров 6844.

№ 2.

Швейный цех изготовляет халаты и куртки. На пошив одного халата расходуется 4 м ткани, а на пошив одной куртки - 3 м ткани. В цехе имеется 84 м ткани. Нужно сшить не более 14 халатов и не более 12 курток. Один халат стоит 160 рублей, а одна куртка - 530 рублей. Сколько нужно сшить халатов и курток для получения наибольшей прибыли от реализации продукции?

Решение:

Пусть - нужно сшить халатов, а - нужно сшить курток.

Составим целевую функцию из соображений, что прибыль должна быть максимальной.

Целевая функция будет иметь вид .

Используя данные из таблицы, составим систему неравенств-ограничений, которым должно удовлетворять решение задачи. Система имеет вид:

(5)

Так как в задаче всего 2 переменных, то удобно применять графический подход. В системе координат изобразим решение системы неравенств (5) и выделим многоугольник решений.

1)

2) - вертикальная прямая

3) - горизонтальная прямая,

4)- оси координат.

ОABCD - многоугольник решений.

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

Точка B– точка выхода, ее координаты являются решением задачи. Найдем координаты точки, решив систему:

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

Ответ: нужно сшить 12 халатов и 12 курток, прибыль составит руб.

№ 3.

Для сохранения здоровья и работоспособности человек должен употреблять некоторое количество белков, жиров, углеводов и витаминов в сутки. Имеются два вида пищи I и II. Содержание питательных веществ в 1 кг пищи, суточная норма и стоимость 1 кг пищи каждого вида даны таблицей:

Как нужно организовать питание, чтобы пища содержала необходимое количество питательных веществ, а стоимость ее была бы минимальной?

Решение:

Пусть кг – требуется потреблять в сутки пищи I , а кг - требуется потреблять в сутки пищи II.

Составим целевую функцию из соображений, что стоимость потребляемой пищи должна быть минимальной.

Целевая функция будет иметь вид .

Используя данные из таблицы, составим систему неравенств-ограничений, которым должно удовлетворять решение задачи. Система имеет вид:

(6)

Так как в задаче всего 2 переменных, то удобно применять графический подход. В системе координат изобразим решение системы неравенств (6) и выделим многоугольник решений.

1)

2)

3)

4) - горизонтальная прямая,

5) - оси координат.

ABCDEF - многоугольник решений (бесконечная область)

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

Точка С – точка входа, ее координаты являются решением задачи. Найдем координаты точки, решив систему:

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

Ответ: требуется потреблять в сутки пищи I 1 кг и пищи II 4 кг, стоимость рациона 210 руб.

№4.

Из 4-х видов сырья производится продукция двух наименований П1 и П2. Количество сырья, необходимое для производства единицы продукции, запасы сырья и прибыль от реализации единицы продукции приведены в таблице.

Найти оптимальный выпуск продукции П1и П2, обеспечивающий максимальную прибыль.

Решение:

Пусть ед. - требуется производить продукции П1, а ед. - требуется производить продукции П2.

Составим целевую функцию из соображений, что прибыль должна быть максимальной.

Целевая функция будет иметь вид

Используя данные из таблицы, составим систему неравенств-ограничений, которым должно удовлетворять решение задачи. Система имеет вид:

(7)

Так как в задаче всего 2 переменных, то удобно применять графический подход. В системе координат изобразим решение системы неравенств (7) и выделим многоугольник решений.

1)

2) ,

3) - горизонтальная прямая,

4) - вертикальная прямая,

5) - оси координат.

ОABCDE - многоугольник решений.

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

Точка С – точка выхода, ее координаты являются решением задачи. Найдем координаты точки, решив систему:

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

Ответ: требуется производить 5 ед. продукции П1, 3 ед. - продукции П2,максимальная прибыль составит 500 руб.

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/330009-graficheskij-metod-reshenija-zadach-linejnogo