русс | укр

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

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

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

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


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

При условиях


Дата добавления: 2015-09-15; просмотров: 834; Нарушение авторских прав


Общая постановка задачи линейного программирования. Основные понятия и определения.

Введение в линейное программирование

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

С (x1, x2,…, xj…, xn) → max (min)

при условиях

gi (x1, x2…, xj…, xn) ≤ bi (i = 1… m), где

С, gi – заданные функции;

xj(j = 1… n) – искомые переменные;

bi (i = 1… m) – некоторые действительные числа.

В зависимости от функций C и gi экономико-математические модели подразделяются на: линейные и нелинейные.

На практике широкое применение получили задачи, в которых условия и критерий оптимальности представлены в виде системы линейных уравнений и неравенств.

Линейными называются уравнения и неравенства, в которых неизвестные входят только в первой степени. Такого рода задачи изучаются в разделе математического программирования, который так и называется - линейное программирование.

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

Линейное программирование – наиболее обширный, хорошо разработанный и практически важный раздел.

Использование этих методов имеет ряд существенных преимуществ перед традиционными методами.

1. возможность рассмотрения всех вариантов решения и выбора среди них оптимального;

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



3. высокая степень автоматизации таких задач позволяет одновременно учитывать в задачах большое количество факторов.

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

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

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

Для изготовления двух видов продукции Х1 и Х2 используют четыре вида ресурсов S1, S2, S3, S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в табл.

Виды ресурса Запас ресурса Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
Х1 Х2
S1
S2
S3 -
S4 -
Прибыль, получаемая от единицы продукции, у.д.е.

 

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

 

Решение:

х1, х2 – число единиц продукции (неизвестные задачи);

Для их изготовления потребуется:

(1* х1+3* х2) - единиц ресурса S1;

(2* х1+1* х2) – единиц ресурса S2;

(1* х2) – единиц ресурса S3;

(3* х1) – единиц ресурса S4.

Потребление ресурсов не должно превышать их запасов. Таким образом, можно записать следующую систему неравенств:

Суммарная прибыль составит:

С=2* х1+3* х2 à max

Эту задачу легко обобщить на случай выпуска n видов продукции с использованием m видов сырья.

1. Заданы переменные задачи х12, …xj…xn (j=1..n), где j – порядковый номер переменной.

2. Известны запасы ресурсов производства в количествах b1, b2, …bi,…bm (i=1..m), где i - порядковый номер ресурса.

3. Заданы технико-экономические коэффициенты затрат каждого вида ресурса на единицу каждой переменной, которые обозначаются aij, а – величина коэффициента, i – порядковый номер ресурса, j- порядковый номер переменной. Например, а21 – означает затраты второго вида ресурса на единицу первой переменной.

4. Известны показатели выхода продукции на единицу переменной. Они обозначаются cj.

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

Найти такие значения искомых переменных х1, х2,…,хn, которые обеспечивают максимум прибыли (критерия оптимальности), выражающегося линейной функцией:

C=С1x12x2+…+Сnxn®max

при соблюдении следующих линейных ограничивающих условий:

1. Ограничение по использованию 1-го вида ресурса

a11x1+a12x2+…+a1nxn£b1

2. Ограничение по использованию 2-го вида ресурса

a21x1+a22x2+…+a2nxn£b2

3. Ограничение по использованию m-го вида ресурса

am1x1+am2x2+…+amnxn£bm

4. Ограничения по не отрицательности неизвестных величин:

x1³0, x2³0, xn³0

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

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

 

Питательное вещество Необходимый минимум пит. вещества Число единиц питательных веществ в 1 кг. корма
I II
S1
S2
S3
Стоимость 1 кг. корма, у.д.е.

 

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

Решение:

x1, x2 – количество кормов I и II, входящих в дневной рацион;

Рацион будет включать:

(3* x1+1* x2) – единиц питательного вещества S1;

(1* x1+2* x2) – единиц питательного вещества S2;

(1* x1+6* x2) – единиц питательного вещества S3;

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

Общая стоимость рациона составит:

С=4 x1+6 x2 à min

Для формулировки задачи в общем виде обозначим:

x1, … xj (j=1,…,n) – число единиц корма n-го вида;

b1, …, bi (i=1,…,m) – необходимый минимум содержания в рационе питательного вещества;

aij – число единиц i-го питательного вещества в единице корма j-го вида;

сj – стоимость единицы корма j-го вида.

Тогда экономико-математическая модель задачи примет вид:

Найти такой рацион Х=(x1,x2,…,xj,…,xn), при котором целевая функция достигает минимального значения, при системе ограничений:

C=С1x12x2+…+Сnxn®min



<== предыдущая лекция | следующая лекция ==>
Прикладной объект. | Общая форма


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


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

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

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


 


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

 
 

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

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