Задача ЛИНЕЙНОго ПРОГРАММИРОВАНИя

Примеры задачи линейного программирования

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

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

Рассмотрим некоторые конкретные задачи, математические модели которых представляют собой ЗЛП.

Задача об использовании ресурсов (задача планирования производства). Обозначим х _j (j = 1, 2, ..., п)– число единиц продукции Р_j, запланированной к производству; b_i (i = 1, 2, ..., m) – запас ресур­са S_i; a_ij – число единиц ресурса S_i, затрачиваемого на изготовле­ние единицы продукции Р_j (числа a_ij часто называют технологиче­скими коэффициентами); с _j – прибыль от реализации единицы продукции Р_j. Тогда экономико-математическая модель задачи об использо­вании ресурсов в общей постановке примет вид: найти такой план Х = (х₁, х₂, …, х_п) выпуска продукции, удовлетворяющий системе

и условию

,

при котором функция

принимает максимальное значение.

Задача составления рациона (задача о диете, задача о смесях). Обозначим х _j (j = 1, 2, ..., п)– число единиц корма п-го вида; b_i (i = 1, 2, ..., m) – необходимый минимум содержания в рационе питательного вещества S_i; a_ij – число единиц питательного вещества S_i в единице корма j-го вида; с _j –  стоимость единицы корма j-го вида. Тогда экономико-математическая модель задачи примет вид: найти такой рацион Х = (х₁, х₂, …, х_п), удовлетворяющий системе

и условию

,

при котором функция

принимает максимальное значение.

Задача об использовании мощностей (задача о загрузке обо­рудования). Предприятию задан план производства продукции по времени и номенклатуре: требуется за время T выпустить п₁, п₂,..., п _k еди­ниц продукции Р₁, Р₂..., Р _k. Продукция производится на станках S₁, S₂, …, S _т. Для каждого станка известны производительность а _ij (т.е. число единиц продукции Р _j, которое можно произвести на станке S_i) и затраты b_ij на изготовление продукции Р _j на станке S_i в единицу времени.

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

Составим экономико-математическую модель задачи.

Обозначим х _ij – время, в течение которого станок S_i будет за­нят изготовлением продукции Р _j (i = 1, 2,..., т; j = 1, 2, ..., k).

Так как время работы каждого станка ограничено и не превышает Т, то справедливы неравенства:

Для выполнения плана выпуска по номенклатуренеобходимо, чтобы выполнялись следующие равенства:

Кроме того,

.

Затраты на производство всей продукции выразятся функцией

.

 Экономико-математическая модель задачи об использовании мощностей примет вид: найти такое решение Х = (х₁₁, х₁₂, …, х_mk), удовлетворяющее указанным условиям, при ко­тором функция F принимает минимальное значение.

Задача о раскрое материалов. На раскрой (распил, обработку) поступает материал одного образца в количестве а единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональ­ных числам b₁, b₂, …, b_l (условие комплектности). Каждая единица материала может быть раскроена п различными способами, при­чем использование i-го способа (i = 1, 2, ..., п) дает а_{i k} единиц k-го изделия (k = 1, 2, ..., l).

Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.

Составим экономико-математическую модель задачи.

Обозначим х _i – число единиц материала, раскраиваемыхi-мспособом, и х – число изготавливаемых комплектов изделий.

Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то

.

Требование комплектности выразится уравнениями

.

Очевидно, что

.

Экономико-математическая модель задачи: найти такое реше­ние Х = (х, х₁, х₂, …, х_п), удовлетворяющее указанным условиям, при котором функция F = х принимает максимальное значение.

⇐ Предыдущая123456789Следующая ⇒

Поделиться: