русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 4814; Нарушение авторских прав


 

К типовым (классическим) задачам ЛП относят следующие: задача о пищевом рационе, задача о загрузке оборудования, задача о снабжении сырьем, транспортная задача. Необходимо понять, что перечисленные задачи достаточно универсальны и образуют "оболочки", с помощью которых пользователь может решать свои конкретные задачи, формально не имеющие ничего общего с рационом, сырьем или с транспортом.

 

7.2.2.1. Задача "о пищевом рационе"

 

Пусть ферма откармливает скот, используя 4 вида кормов. Стоимость единицы каждого вида корма равна с1,с2,с3 и с4. Из этих кормов требуется составить рацион, содержащий: белков - не менее b1 единиц, углеводов - не менее b2единиц, жиров - не менее b3 единиц. Для видов кормов содержание белков, углеводов и жиров известно и представлено в таблице 7.1. Требуется составить такой рацион, чтобы условия по белкам, углеводам и жирам были выполнены при минимальной стоимости рациона.

 

Таблица 7.1

Номер вида корма Белки Углеводы Жиры
a11 a21 a31 a41 a12 a22 a32 a42 a13 a23 a33 a43

 

 

Формальная постановка задачи. Обозначим: х1, х2, х3 и х4 - искомые количества видов кормов; L - это стоимость рациона. Ее формула для рассматриваемого примера:

 

L=c1·x1+c2·x2+c3·x3+c4·x4,

или, короче -

4

L= ∑(ci·xi); (7.8)

i=1

Исходя из условия задачи, запишем систему неравенств:

 

a11·x1+a21·x2+a31·x3+ a41·x4b1;

a12·x1+a22·x2+a32·x3+a42·x4b2; (7.9)

a13·x1+a23·x2+a33·x3+a43·x4b3.

 

Тогда, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных х1,х2,х3 и х4, чтобы они удовлетворяли ограничениям (7.9) и одновременно обращали в минимум линейную функцию этих переменных



4

L= ∑(ci·xi)→ min. (7.10)

i=1

В поставленной задаче критерий эффективности L, а искомыми элементами решения являются х1,х2,х3 и х4. Математическая модель представляет собой зависимость (7.10), дополненную системой ограничений (7.9).

 

7.2.2.2. Задача "о планировании производства"

 

Пусть предприятие производит 3 вида изделий, по каждому из которых спущен план, по которому выпуск изделий по видам не может быть менее, соответственно b1,b2 и b3. На изготовление изделий идет 4 вида сырья, запасы которого составляют, соответственно, s1,s2,s3 и s4. Одно изделие каждого вида приносит прибыль (по видам изделий): с1,с2,с3. Потребный расход сырья на каждый вид изделия представлен в таблице 7.2. Требуется так спланировать производство (сколько и каких изделий выпустить), чтобы план был выполнен, а суммарная прибыль была бы максимальной.

 

Таблица 7.2

Номер сырья Изделие № 1 Изделие № 2 Изделие № 3
а11 а12 а13 а14 а21 а22 а23 а24 а31 а32 а33 а34

 

Формальная постановка задачи. Элементами решения будут х1,х2,х3 - количества единиц изделий каждого вида. Условие выполнения плана представим в виде системы неравенств-ограничений:

 

x1b1,x2b2, x3b3; (7.11)

 

Ограниченность сырья на складе представим в виде системы неравенств-ограничений:

 

a11·x1+a21·x2+a31·x3s1;

a12·x1+a22·x2+a32·x3s2;(7.12)

a13·x1+a23·x2+a33·x3s3;

a14·x1+a24·x2+a34·x3s4;

 

Суммарную прибыль L выразим формулой:

L=с1·х1+с2·х2+с3·х3.

 

Тогда, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных х1,х2,х3, чтобы они удовлетворяли ограничениям (7.11, 7.12) и одновременно обращали в максимум линейную функцию этих переменных, т.е.

3

L=∑(ci·xi)→ max. (7.13)

i=1

В поставленной задаче критерий эффективности L, а искомыми элементами решения являются х1,х2,х3. Математическая модель представляет собой выражение (7.13), дополненное системой ограничений (7.11) и (7.12).

 

7.2.2.3. Задача "о загрузке оборудования"

 

Пусть фабрика располагает двумя видами станков, соответственно n1 и n2 штук каждого вида. Станки могут производить 3 вида тканей с производительностью, указанной в таблице 7.3. Каждый метр ткани (по их видам) приносит доход, соответственно, c1,c2 и c3. Фабрике предписан план, согласно которому она должна производить в месяц (по видам ткани) не менее b1,b2 и b3 метров ткани. Для исключения затоваривания торговли объем выпуска тканей не должен превышать (по видам ткани) d1,d2 и d3 метров. Кроме того, все без исключения станки должны быть загружены. Требуется так спланировать загрузку станков, чтобы суммарный месячный доход L был максимален.

 

Таблица 7.3

Номер типа станка Ткань № 1 Ткань № 2 Ткань № 3
а11 а21 а12 а22 а13 а23

 

Формальная постановка задачи. Элементами решения являются не количество ткани по видам, а количество станков, занятых производством той или иной ткани. Так как видов станков 2, а видов ткани 3, то удобнее элементы решения обозначить двумя индексами (первый - вид станка, второй - вид ткани): х11,х12,х13,x21,х22,х23.

Ограничения по обеспечению плана имеют вид:

a11·x11+a21·x21b1;

a12·x12+a22·x22b2; (7.14)

a13·x13+a23·x23b3.

 

Ограничения по исключению затоваривания имеют вид:

 

a11·x11+a21·x21d1;

a12·x12+a22·x22d2; (7.15)

a13·x13+a23·x23d3.

 

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

х11+х12+х13=n1;

x21+x22+x23=n2. (7.16)

 

Суммарное количество метров ткани первого вида, произведенное всеми станками, будет равно a11·x11+a21·x21 и принесет доход c1·(a11·x11+a21·x21). Рассуждая аналогично для фабрики месячный доход равен:

 

L=c1·(a11·x11+a21·x21) +c2·(a12·x12+a22·x22) +c3·(a13·x13+a23·x23),

 

или короче:

 

2 3

L=∑(cj) ·∑(aij·xij). (7.17)

j=1 i=1

 

Тогда, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных х11,х12,х13,x21,x22,x23, которые должны удовлетворять ограничениям-неравенствам (7.14, 7.15), удовлетворять ограничениям-равенствам (7.16) и одновременно обращали в максимум линейную функцию этих переменных (7.17), т.е.

2 3

L=∑(cj) ·∑(aij·xij)→ max. (7.18)

j=1 i=1

Математическая модель представляет собой (7.18) и систему ограничений (7.14, 7.15, 7.16).

 

7.2.2.4. Задача "о поставке сырья"

 

Пусть имеются 3 предприятия, требующих, соответственно, а1,а2 и а3 единиц сырья. Имеются 5 складов сырья, обеспечивающих стоимости поставок сырья, указанные в таблице 7.4. Запас сырья на базах равен, соответственно, b1,b2,b3,b4 и b5 единиц сырья. Требуется составить такой план снабжения предприятий сырьем (с какой базы, куда и сколько сырья везти), чтобы потребности предприятий были обеспечены при минимальных расходах на сырье.

 

Таблица 7.4

№ предприятия Склад № 1 Склад № 2 Склад № 3 Склад № 4 Склад № 5
с11 с21 с31 с12 с22 с32 с13 с23 с33 с14 с24 с34 с15 с25 с35

 

Формальная постановка задачи. Обозначим через xij количество сырья, получаемое i-м предприятием с j-го склада. Всего план будет состоять из 15 элементов решения:

 

x11,x12,x13,x14,x15,x21,x22,x23,x24,x25, x31,x32,x33,x34,x35.

 

Ограничения-равенства по потребностям:

 

x11+x12+x13+x14+x15=a1;

x21+x22+x23+x24+x25=a2; (7.19)

x31+x32+x33+x34 +x35=a3.

 

Ограничения-неравенства, вытекающие из возможностей складов:

 

x11+x21+x31b1;

x12+x22+x32b2;

x13 +x23+x33b3; (7.20)

x14 +x24+x34b4;

x15+x25+x35b5.

 

С учетом таблицы 7.4, пользуясь знаком двойной суммы, получим суммарные расходы на сырье:

3 5

L=∑ ∑(сij·xij)→ min. (7.21)

i=1 j=1

Математическая модель представляет собой (7.21) и систему ограничений (7.19, 7.20), а поставленная задача сводится к нахождению неотрицательных значений элементов решения xij, при условии, что они удовлетворяют системе ограничений.

 

7.2.2.4. Транспортная задача (задача "о перевозках")

 

Пусть имеются m пунктов отправления, в которых сосредоточены грузы в количестве, соответственно, a1,a2,...,am единиц. Кроме того, имеются n пунктов назначения, требующих, соответственно, b1,b2,...,bn единиц груза. Сумма всех заявок равна сумме всех запасов. Известны стоимости cij перевозки единицы груза от каждого пункта отправления, до каждого пункта назначения. Требуется составить такой план перевозок (откуда, куда и сколько единиц), чтобы все заявки были выполнены, а общая стоимость всех перевозок минимальна.

Формальная постановка задачи. Обозначим через xij количество единиц груза, отправляемого из i-го пункта отправления в j-й пункт назначения. Совокупность чисел xij будем называть "планом перевозок", а сами величины xij - "перевозками". Эти неотрицательные переменные должны удовлетворять следующим условиям:

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

 

x11+x12+ ... +x1n=a1;

x21+x22+ ... +x2n=a2; (7.22)

...

xm1+xm2+ ... +xmn=am.

 

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

 

x11+x21+ ... +xm1=b1;

x12+x22+ ... +xm2=b2; (7.23)

...

x1n+x2n+ ... +xmn=bn.

 

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

m n

L=∑ ∑(сij·xij)→ min. (7.24)

i=1 j=1

Знак двойной суммы означает, что суммирование производится по всем комбинациям индексов i и j, т.е. по всем парам пунктов назначения и пунктов отправления.

Математическая модель представляет собой (7.24) и систему ограничений (7.22, 7.23), а поставленная задача сводится к нахождению неотрицательных значений элементов решения xij, при условии, что они удовлетворяют системе ограничений.

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



<== предыдущая лекция | следующая лекция ==>
Общая постановка задачи линейного программирования | Графическое решение задач линейного программирования


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.011 сек.