Задача ЛИНЕЙНОго ПРОГРАММИРОВАНИя
Понятие линейного программирования. Линейное программирование – раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.
Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда вытекает необходимость разработки новых методов.
Рассмотрим некоторые конкретные задачи, математические модели которых представляют собой ЗЛП.
|
|
Задача об использовании ресурсов (задача планирования производства). Обозначим хj (j = 1, 2,..., п)– число единиц продукции Рj,запланированной к производству; bi (i = 1, 2,..., m) – запас ресурса Si; aij – число единиц ресурса Si, затрачиваемого на изготовление единицы продукции Рj (числа aij часто называют технологическими коэффициентами); сj – прибыль от реализации единицы продукции Рj. Тогда экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план Х = (х 1, х2, …, хп) выпуска продукции, удовлетворяющий системе
и условию
,
при котором функция
принимает максимальное значение.
Задача составления рациона (задача о диете, задача о смесях). Обозначим хj (j = 1, 2,..., п)– число единиц корма п -го вида; bi (i = 1, 2,..., m) – необходимый минимум содержания в рационе питательного вещества Si; aij – число единиц питательного вещества Si в единице корма j -го вида; сj – стоимость единицы корма j -го вида. Тогда экономико-математическая модель задачи примет вид: найти такой рацион Х = (х 1, х 2, …, хп), удовлетворяющий системе
и условию
,
при котором функция
принимает максимальное значение.
Задача об использовании мощностей (задача о загрузке оборудования). Предприятию задан план производства продукции по времени и номенклатуре: требуется за время T выпустить п 1, п 2 ,..., пk единиц продукции Р 1, Р 2 ..., Рk. Продукция производится на станках S1, S2, …, Sт. Для каждого станка известны производительность аij (т.е. число единиц продукции Рj, которое можно произвести на станке Si) и затраты bij на изготовление продукции Рj на станке Si в единицу времени.
|
|
Необходимо составить такой план работы станков (т.е. так распределить выпуск продукции между станками), чтобы затраты на производство всей продукции были минимальными.
Составим экономико-математическую модель задачи.
Обозначим хij – время, в течение которого станок Si будет занят изготовлением продукции Рj (i = 1, 2,..., т; j = 1, 2,..., k).
Так как время работы каждого станка ограничено и не превышает Т, то справедливы неравенства:
Для выполнения плана выпуска по номенклатуренеобходимо,чтобы выполнялись следующие равенства:
Кроме того,
.
Затраты на производство всей продукции выразятся функцией
.
Экономико-математическая модель задачи об использовании мощностей примет вид: найти такое решение Х = (х 11, х 12, …, хmk), удовлетворяющее указанным условиям, при котором функция F принимает минимальное значение.
Задача о раскрое материалов. На раскрой (распил, обработку) поступает материал одного образца в количестве а единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам b 1, b 2, …, bl (условие комплектности). Каждая единица материала может быть раскроена п различными способами, причем использование i -го способа (i = 1, 2,..., п) дает аik единиц k -го изделия (k = 1,2,..., l).
Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.
Составим экономико-математическую модель задачи.
Обозначим хi – число единиц материала, раскраиваемых i -мспособом, и х – число изготавливаемых комплектов изделий.
Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то
.
Требование комплектности выразится уравнениями
.
Очевидно, что
.
Экономико-математическая модель задачи: найти такое решение Х = (х, х 1, х 2, …, хп), удовлетворяющее указанным условиям, при котором функция F = х принимает максимальное значение.