Решения задач в MathCAD

 

 

 

СОДЕРЖАНИЕ 
 

ВВЕДЕНИЕ…………………………………………………………………………4

1 ПОСТАНОВКА ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ДЛЯ N ПЕРЕМЕННЫХ……………………………………………………………5

2.ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ (ТЗ) ДЛЯ N

ПЕРЕМЕННЫХ…………….....................................................................................7

3.ПРИМЕР РЕШЕНИЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ………………………………………………………...10

4ПРИМЕР РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ………………………………....12

ЗАКЛЮЧЕНИЕ………………………………………………………………….19

СПИСОК  ЛИТЕРАТУРЫ…………………………………………………………20   
 

 

ВВЕДЕНИЕ 

    Про линейное

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

      Первая версия пакета MathCAD появилась в 1986г. Пакет  постоянно  совершенствуется. В настоящее время существуют версии MathCAD, работающие под Windows.

    цель 
 
 
 
 
 
 
 
 
 

 

1 ПОСТАНОВКА ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ДЛЯ N ПЕРЕМЕННЫХ 

    Рассмотрим  задачу формирования плана производства: некоторое предприятие может выпускать определённый набор продукции.

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

    Построение экономико-математической модели:

    n - число различных видов продукции.

    m - число различных ресурсов.

    aij - объём i-того ресурса, который расходуется на производство одной единици j-того вида продукции i=1..m, j=1..n.

    Xj - объем (количество единиц) j-того вида продукции в производственном плане предприятия (j от 1 до n).

    Прибыль обозначим F, тогда F=c₁X₁+c₂X₂+...+c_nX_n->=max

    Составим  ограничения для первого ресурса:

    а₁₁ - объем первого ресурса, который расходуется на производство одной единицы первого вида продукции;

    а₁₁Х₁ - объём первого ресурса, который требуется на изготовление Х₁ единиц первого вида продукции;

    а₁₂Х₂ - объём первого ресурса, который требуется на изготовление Х₂ единиц второго вида продукции;

    а_1nХ_n - объём первого ресурса, который требуется на изготовление Х_n единиц n-ого вида продукции;

    а₁₁Х₁+a₁₂X₂+...+a_1nX_n - объём первого ресурса, который требуется на изготовление продукции, следовательно, мы имеем следующее ограничение: 

    а₁₁Х₁+а₁₂+...+а_1nX_n<= b₁

    Аналогично  для остальных ресурсов:

    а₂₁Х₁+а₂₂+...+а_2nX_n<=b₂

    а₃₁Х₁+а₃₂+...+а_3nX_n<=b₃

      .........................................

       а_m1Х₁+а_m2+...+a_mnX_n<=b_m

    Кроме того, количество выпущенной продукции  не может быть отрицательной, следовательно, Х₁>= 0, X₂>=0, ...,X_n>=0. 

 

     2 ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ (ТЗ) ДЛЯ N ПЕРЕМЕННЫХ 

    Пусть имеется несколько поставщиков  однородной продукции (каждый с определенным запасом) и несколько потребителей этой продукции (с известными потребностями  у каждого). Задана также сеть коммуникаций (дорог, рек, воздушных линий и  т.д.) связывающая каждого поставщика с каждым потребителем. На каждой коммуникации задана цена перевозки – стоимость  перевозки единицы продукции. Если какая – либо коммуникация отсутствует, то считаем, что она есть, но цену перевозки на ней устанавливаем равной бесконечности (+∞). Это соглашение сделает невыгодным перевозку по ней и автоматически исключит данную коммуникацию из плана перевозок.

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

    Транспортные  задачи бывают:

    1) открытые m ≠ n (суммарный запас продукции, имеющейся у поставщиков, не совпадает с суммарной потребностью в продукции у потребителей.)

    2) Закрытые m = n (суммарный запас продукции, имеющейся у поставщиков, совпадает с суммарной потребностью в продукции у потребителей.)

    Метод потенциалов «работает» только для  закрытых ТЗ, причем, закрытая ТЗ всегда разрешима.

    Открытую ТЗ сводят к закрытой ТЗ путем прибавления к суммарному запасу продукции или суммарной потребности продукции недостающих единиц до равенства суммарного запаса продукции и суммарной потребности продукции.

    Закрытая  транспортная задача формулируется  как Задача Линейного Программирования (ЗЛП) следующего вида:

    

      
 
 

     , где 

     - запас i – го поставщика

     - потребность j – го потребителя

     - цена перевозки единицы продукции  по коммуникациям (i,j)

    (от  i – го поставщика к j – му потребителю)

     - объем перевозки продукции (неизвестный)  по коммуникациям (i,j).

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

    Структура матрицы ограничений транспортной задачи такова, что столбец, соответствующей  переменной содержит ровно два ненулевых элемента: единицу в строке с номером i и единицу в строке m + i.

    Вектор  двойственных переменных Y = ( ,…, , ,…, ) имеет m + n компонент (по числе ограничений ТЗ), которые называются потенциалами: переменные , ,…, - потенциалы поставщиков; переменные , …, - потенциалы потребителей.

    Используя схему для построения двойственной задачи к ЗЛП в стандартной  форме, имеем:  

      

    В полученной двойственной задаче n·m ограничений, соответствующих каждой переменной ТЗ. Вспоминая, что невязка между левой и правой частью в ограничений двойственной задачи есть оценка для соответствующей переменной исходной задачи , запишем условия оптимальности текущего плана перевозок в ТЗ:  

     . 

    Неизвестные потенциалы и (их общее количество равно m + n) могут быть найдены (и именно так отыскиваются) из условия равенства нулю оценок для базисных переменных (заполненных клеток таблицы) ТЗ (таких равенств (m+n - 1), что следует из замечания ниже). 

      ,  

    для заполненных клеток (i,j) таблицы ТЗ.

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

 

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

    Решим задачу линейного программирования симплекс – методом :

    f(x) = 2x₁ + 3x₂ + 4x₃→ max

    3x₁ + x₂ + 3x₃<=5

    5x₁ + 4x₂ + 4x₃<=12

    2x₁ + x₂ + 2x₃<=8

    x₁>=0; x₂>=0; x₃>=0;

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

 

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

    По  заполненной симплекс таблице определяем решение, соответствующее этой (нулевой) итерации. Свободные переменные равны 0. Базисные переменные и значение функции  находим из таблицы. Они представлены в столбце «значение». Отметим, что значение функции цели берём с противоположенным знаком. Итак, x° = (0,0,0,5,12,8) f° = 0.

    В оценочной строке имеются положительные  числа. Значит, решение можно улучшить. Выбираем наибольшее из положительных  чисел. Если таких чисел несколько  – берём любое из них. Соответствующий  столбец называют ведущим. По ведущему столбу и столбцу «значения» определяем оценку для каждой строки. Число из столбца «значение» делим на строку. По условию задачи это положительное число. Объявляем ведущей строку ту, оценка у которой наименьшее положительное число.

    В первой таблице ведущая строка и  столбец выделен цветом. На их пересечении  находится ведущий элемент. В  нашем случае это 3.

    Переходим к первой итерации. Её суть состоит  в том, чтобы свободную x₃ сделать базисной, а базисную переменную x₄ - свободной. В таблице выполняем преобразования аналогичные элементарным строчным преобразования аналогичные элементарным строчным преобразованиям в методе Гаусса при решении системы линейных уравнений. В результате преобразований получим: