Элементы матричной алгебры




НазваниеЭлементы матричной алгебры
страница7/24
Дата публикации23.06.2013
Размер1.64 Mb.
ТипДокументы
lit-yaz.ru > Математика > Документы
1   2   3   4   5   6   7   8   9   10   ...   24
^

2.6. Преобразование канонической формы модели в симметричную.



Пусть модель задачи линейного программирования задана в канонической форме.

(2.5)

(2.6)

max (2.7)

Для преобразования этой модели в симметричную необходимо перейти от системы ограничений равенств (2.5) к эквивалентной системе неравенств. Для этого приведем систему уравнений (2.5) к единичному базису. Пусть базисными переменными будут первые m переменных. . После приведения к единичному базису система (2.5) примет вид:

(2.8)

В системе уравнений (2.8) каждая базисная переменная входит только в одно уравнение с коэффициентом единица, поэтому к каждому уравнению можно применить сформулированную ранее лемму 1. Согласно этой лемме каждое уравнение вида при условии, что , можно заменить эквивалентным неравенством . Сформулируем правило преобразования системы ограничений –равенств в эквивалентную систему неравенств:

  • приводим систему уравнений к единичному базису;

  • отбрасываем базисные переменные и заменяем знак равенства на знак неравенства типа .

Так как отброшенные базисные переменные больше не входят в систему условий задачи, необходимо избавиться от них и в целевой функции. Для этого осуществляем следующие действия:

  • выразим базисные переменные через свободные из системы (2.8):

(2.9)

  • подставим (2.9) в функцию цели (2.7).

Исключение базисных переменных из функции цели можно осуществлять одновременно с приведением системы ограничений к единичному базису. Для этого следует записать целевую функцию (2.7) в виде: (2.10)

и рассматривать условие (2.10) как дополнительное ограничение системы условий.

Пример 2.2. Преобразовать каноническую форму модели в симметричную.





Запишем целевую функцию:

Для приведения к единичному базису составим таблицы Гаусса.

Таблица 2.3

№ иттер.F(X)x1x2x3x4x5B001–12–31–2Главный элемент a11=102301–160–12–120311–22120

101–12–31–2Главный элемент a33=1005–47–3100011–11110–10412

201–30–1–1–4

Главный элемент a25=1009031140011–11110–10412

301602010система приведена к

единичному базису

переменных (x1, x5 ,x3)0090311400–81–40–1310–10010–12Запишем соответствующие последней итерации систему уравнений и целевую функцию.

^ F(x)=

Чтобы получить симметричную модель, отбросим в системе уравнений базисные переменные (x1, x2, x4) и заменим знак равенства на знак неравенства типа .:



F(x)= max
  1. ^

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



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

1. Задача планирования производства

Эту задачу также иногда называют задачей об использовании ресурсов или задачей оптимального ассортимента.

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

m – число ресурсов, n – число товаров;

аijчисло единиц i-го ресурса, необходимое для производства единицы j-го товара;

bi максимальное число единиц i-го ресурса, имеющееся в распоряжении фирмы,

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

Сведем все исходные данные в следующую таблицу.
  • Товар




  • РесурсНормы затрат ресурса на ед. продуктаОбъем ресурсаП1П2ПnB1a11a12A1nb1B2a21a22A2nb2Bmam1am2amnbmПрибыльс1с2сnПостроим математическую модель.

Обозначим хj – запланированный фирмой уровень производства j-го товара, тогда

– общий план производства.

Общее количество i-го ресурса, используемого согласно общему плану производства , равно

Так как эта величина не должна превосходить запаса (наличия) i-го ресурса, получаем для каждого ресурса линейное неравенство вида:



Из экономического смысла переменных следует, что

Доход, получаемый от производства хj единиц j-го товара, равен .

Задача состоит в отыскании плана , обращающего функцию дохода в максимум и удовлетворяющего ограничениям по объемам ресурсов и условию неотрицательности переменных

Получили задачу линейного программирования в симметричной форме.
2. Задача диеты (задача разработки рационального рациона кормления)
Является одним из первых применений линейного программирования к практическим потребностям. Эта задача в различных формулировках применима к самым различным приложениям. Сформулируем задачу.

Различные пищевые продукты содержат питательные вещества и витамины в определенных, но различных пропорциях. Минимальные потребности в тех или иных веществах и витаминах известны. Зная величину запасов различных продуктов и стоимость каждого, необходимо определить, как можно удовлетворить потребности при минимальных затратах.

Ведем обозначения: m–число химических веществ, n–число имеющихся в распоряжении различных видов продуктов;

аij – количество единиц i-гo химического вещества, содержащегося в единице j-го продукта,

bi минимальная дневная потребность в i-м химическом веществе,

cj – стоимость единицы j-го продукта,

Сведем все исходные данные в следующую таблицу.
  • Продукт


  • ВеществоНормы содержания химических веществ на ед. продуктаМиним. норма потребления. химич. веществаП1П2ПnB1a11a12a1nB1B2a21a22a2nB2Bmam1am2amnBmЦенас1с2сnПостроим математическую модель.

Обозначим хj –количество единиц jго продукта, используемое в диете, тогда

– вектор диеты ( диета).

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

Поскольку каждое из этих количеств ( ) не может быть меньше минимальной дневной нормы потребностей в i–том химическом веществе, для каждого i получим линейное неравенство вида:

Поскольку отрицательные значения хj. не имеют смысла, требуем, чтобы

Стоимость одного продукта, используемого в диете, равняется . Тогда стоимость всей диеты:

Задача состоит в отыскании вектора диеты , минимизирующего функцию и удовлетворяющего условиям:

Получили задачу линейного программирования в симметричной форме.

Задача об оптимальном раскрое материалов.

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

Полуфабрикаты поступают на предприятие в виде листов фанеры, стали, стекла. Из полуфабрикатов требуется изготовить возможно большее число комплектов деталей. При этом должны быть соблюдены следующие условия:

  • комплект состоит из m разных деталей, причем в комплект входит рk деталей k-го типа.

  • всего имеется n партий материала, причем i-я партия содержит qi единиц.

  • единица каждой партии может раскраиваться s различными способами.

Пусть при j-ом способе раскроя одной единицы i-ой партии полуфабрикатов получается деталей k-го типа. Обозначим через – количество единиц i-й партии материалов, которые следует раскроить по j-му способу. Количество деталей k-го типа, которое будет при этом получено, равно . Количество деталей k-го типа, которое можно получить из i–ой партии полуфабрикатов, используя все способы раскроя, равно . Общее число деталей k-го типа можно получить, если сложить количества деталей этого вида, выкраиваемых из каждой партии материалов:

Каждый комплект содержит рk деталей k-го типа. Поэтому количество комплектов, обеспеченных деталями k-го типа, равно:



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

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



Получили задачу линейного программирования в общей форме.

Задача может иметь и несколько другую постановку: найти план раскроя, обеспечивающий минимум израсходованного материала. Рассмотрим такую задачу.

Листы материала размером 613 м2 нужно раскроить так, чтобы получились заготовки 2–х типов: 800 штук типа А и 400 штук типа В ( 23 м2, израсходовав минимальное количество материала.

Пусть известны способы раскроя.

  1. ЗаготовкиСпособы1234А3210В16913Обозначим – число листов материала, раскраиваемое j-ым способом. Тогда –план раскроя.

Математическая модель задачи может быть записана следующим образом: найти минимум функции при условиях


1   2   3   4   5   6   7   8   9   10   ...   24

Похожие:

Элементы матричной алгебры iconКурсовая работа по дисциплине «Информатика» на тему «Применение алгебры...
Элементы алгебры высказываний. Примеры использования алгебры высказываний в информатике

Элементы матричной алгебры iconКурсовая работа по информатике на тему: «применение алгебры высказываний в информатике»
Алгебра – это наука, которая изучает множество некоторых элементов и действия (операции) над ними. Если элементы алгебры – натуральные...

Элементы матричной алгебры iconКонспект урока на тему «Основы логики (повторение). Решение логических...
Основы логики; познакомить учащихся с методами решения логических задач; формирование у учащихся практических умений и навыков решения...

Элементы матричной алгебры iconМетод «от пролога к эпилогу»
«все его элементы суть элементы смысловые» (Лотман Ю.). Исходя из этих положений, выделяем основные приемы, опробуем их на уроке

Элементы матричной алгебры iconЭлементы радиочастотных линий передачи
Элементы радиочастотных линий передачи: Учебно-методическое пособие по курсу «Устройства свч и антенны» / В. В. Паслен, Е. С. Нестругина....

Элементы матричной алгебры iconДипломной практике «система управления ртк для обработки сложных поверхностей»
Обычно изделия изготавливаются из мягких цветных металлов, пластика или дерева. Это могут быть элементы орнамента для декорирования...

Элементы матричной алгебры iconУрок по геометрии в 8 классе на тему «теорема пифагора»
Осуществление межпредметной связи алгебры с географией, историей, литературой, геометрией

Элементы матричной алгебры icon15. Уроки алгебры Кирилла и Мефодия,10-11 класс
МАрк sql. Автоматизированная информационно-библиотечная система. Версия для школьных библиотек

Элементы матричной алгебры iconРабочая программа факультативного курса «Элементы статистики и теории вероятностей»
«Элементы комбинаторики, статистики и теории вероятностей». Так как в этом году учащиеся 9 класса изучают программный материал по...

Элементы матричной алгебры iconИсследование свойств алгебры множеств
Цель работы: Изучение множества, его подмножеств и законов сочетания подмножеств, образующих алгебраическую систему, называемую булевой...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница