Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Постановка задачи. Рассмотрим несколько примеров задач линейного программирования (ЗЛП)




 

Рассмотрим несколько примеров задач линейного программирования (ЗЛП).

Задача о пищевом рационе (задача о диете, задача о смесях).

Ферма производит откорм скота с коммерческой целью. Пусть имеются четыре вида продуктов: Р1, Р2, Р3, Р4 со стоимостью с1, с2, с3, с4 соответственно. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков – не менее b1 единиц, углеводов – не менее b2 единиц, жиров – не менее b3 единиц. Для продуктов Р1, Р2, Р3, Р4 содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано таблицей.

Продукт Элементы
Белки Углеводы Жиры
Р1 Р2 Р3 Р4 a11 a21 a31 a41 a12 a22 a32 a42 a13 a23 a33 a43

 

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

Составим математическую модель этой задачи. Пусть x1, x2, x3, x4 – количества продуктов Р1, Р2, Р3, Р4 соответственно, входящих в рацион. Целевая функция (стоимость рациона) будет иметь вид:

.

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

(2.1)

Таким образом, задача сводится к следующей: найти такие неотрицательные значения переменных x1, x2, x3, x4, чтобы они удовлетворяли неравенствам (2.1) и обращали в минимум целевую функцию:

.

Задача об использовании сырья (задача планирования производства).

Из сырья двух видов 1 и 2, запасы которого ограничены и составляют b1 и b2 единиц соответственно, изготавливается продукция трех видов. Затраты сырья на производство продукции задаются следующей таблицей.

 

Вид сырья Затраты сырья на 1 ед. продукции вида
a11 a21 a12 a22 a13 a23

 

Прибыль от производства единицы продукции j-го вида составляет cj рублей
(j = 1,2,3). Требуется найти такой план выпуска продукции, при котором сырье не будет перерасходовано, а суммарная прибыль окажется максимальной.

Обозначим x1, x2, x3 соответственно количество производимой продукции 1-го, 2-го и
3-го видов. Тогда математическая модель задачи имеет вид:

 

Задача об использовании мощностей (задача о загрузке оборудования).

Ткацкая фабрика располагает двумя видами станков: N1 станков типа 1 и N2 станков типа 2. Станки могут производить три вида тканей: Т1, Т2, Т3, но с разной производительностью. Станок типа i производит в месяц aij метров ткани вида Tj. Каждый метр ткани вида Tj приносит прибыль сj (j = 1,2,3). Согласно плану, фабрика должна производить в месяц не менее bj метров ткани Tj. Кроме того, все станки должны быть загружены. Требуется так распределить загрузку станков, чтобы суммарная месячная прибыль была максимальной.

Пусть xij – количество станков типа i (i = 1, 2), занятых производством ткани
Tj (j = 1, 2, 3). Тогда должны выполняться следующие ограничения:

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

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

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

 

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

(2.2)

 

где aij, bi, cj ( , ) – заданные постоянные величины. Среди ограничений могут одновременно встречаться знаки ≤, =, ≥.

Определение 2.1.Вектор , удовлетворяющий системе ограничений (2.2), называется допустимым решением или планом ЗЛП. Множество всех планов называется допустимой областью или областью допустимых решений. План, который доставляет максимум (минимум), целевой функции называется оптимальным планом или оптимальным решением ЗЛП. Таким образом, решить ЗЛПзначит найти ее оптимальный план.

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

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

,

, ,

где , .

Эта стандартная форма называется основной задачей линейного программирования (ОЗЛП). Запишем ее в матричном виде

 

 

при ограничениях Ax = b, x ≥ 0.

Здесь

, , , ,

 

T означает транспонирование, т. е. сT – вектор-строка, . A, b, c предполагаются известными, причем b ≥ 0.

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

1. Минимизация целевой функции f равносильна максимизации функции g = –f.

2. Ограничение в виде неравенства равносильно уравнению при условии, что дополнительная переменная . Аналогично,

3. Если на некоторую переменную xj не накладывается условие неотрицательности, то делают замену переменной , , .

 

 


Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой





Дата добавления: 2014-11-10; просмотров: 1884. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.021 сек.) русская версия | украинская версия
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7