Контрольная работа по "Математическое Моделирование"

Задание 1. Решить транспортную задачу. 

 
 

В ячейки B4:D6 заносится матрица цен, далее в ячейки B11:D13 помещаются любые значения больше нуля. В ячейках G11:G13, вычисляются суммы ячеек B11:D11; B12:D12; B13:D13) соответственно. В B14:D14, вычисляются суммы ячеек (B11:B13; C11:C13; D11:D1) соответственно. В ячейку F16 записывается следующая формула: "=СУММПРОИЗВ B11:F13;B4:F6", вычисляющая произведение соответствующих элементов массивов, а затем суммирует получившиеся значения.  Далее выделив ячейки B11:F13 вызываем формат ячеек и в закладке "Число", выставляем число десятичных знаков равным нулю.  
 
В окне поиска решений, выставляем все ограничения и нажимаем “Enter”, в итоге получаем оптимальный план грузоперевозок и сумму минимальных затрат на эти перевозки. 

Задание 2. Определить продуктивность матрицы А.

 
 

   Задание 3. Дана матрица 

                    

   Пусть конечный продукт Y = (y₁, y₂, y₃) должен быть в размере

    y₁  =10⁵ у.е., y₂ =20⁵ у.е., y₃ =15⁵ у.е. . Найти валовые выпуски отраслей, обеспечивающие заданное  конечное потребление, и матрицу полных затрат. 
 
 
 

    Решение:

 
 
    

    Задание 5. Дана структурная матрица торговли 4-х стран. Найти бюджетный вектор бездефицитной торговли 4-х стран , если сумма бюджетов составляет 2 триллиона у.е.                                                                                                       

А 

Вводим единичную  матрицу Е.

 

А-Е

 

(A-E)обр (без первой строки, с добавленной нижней = 1)

 

Ответ: 364.08;   422,33;   703,88;   509,7087. 

Задание 6.  Решить следующую задачу ЛП в канонической форме симплекс-методом. (1.1)

      (1.2)

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

   Идея  симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника  допустимых решений (начальное допустимое базисное решение). Затем нужно проверить  это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине  многогранника и вновь проверить  на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число "шагов" мы найдем искомую  точку минимума или максимума. Надо заметить, что при переходе от одной  вершины к другой значение целевой  функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).

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

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

            (1.3)

Следовательно, базисными являются переменные x₂, x₄, x₅, x₆, им придаем значения, равные свободным членам соответствующих строк: x₂=40, x₄=20, x₅=10, x₆=30, . Переменные x₁ и x₃ являются небазисными: x₁=0, x₃=0 .

Построим начальное  допустимое базисное решение 

        (1.4)

Для проверки на оптимальность найденного решения  x⁰ нужно из целевой функции исключить базисные переменные (с помощью системы (1.2 ) и построить специальную симплекс таблицу.

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

        (1.5)

Теперь при  помощи (1.2) –(1.4) составляем начальную симплекс-таблицу:

В нулевую строчку  записаны коэффициенты с обратным знаком соответствующих переменных при  целевой функции. Критерий оптимальности (для задачи на поиск минимума): допустимое базисное решение(x⁰) оптимально, если в нулевой строчке нет ни одного строго положительного числа (не считая значения целевой функции (880)). Это правило распространяется и на следующие итерации (таблицы). Элементы нулевой строки будем называть оценками столбцов.

Так что начальное  допустимое базисное решение (1.3) неоптимально: 7>0, 14>0.

В нулевом столбике записаны значения базисных переменных. Они обязательно должны быть (неотрицательными От первой по четвертую строки написаны коэффициенты переменных из системы (1.2).

Так как x⁰ неоптимально, то надо перейти к другой вершине многогранника допустимых решений (построить новое д.б.р.). Для этого нужно найти ведущий элемент и провести определенное преобразование (симплексное преобразование).

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

В таблице 1 ведущий  столбик - третий столбик, и ведущая  строка - четвертая строка (min{40/1,30/1}=30/1) обозначены стрелками, а ведущий элемент - кружочком. Ведущий элемент показывает, что базисную переменную x₆ нужно заменить на небазисную x₃ . Тогда новыми базисными переменными будут x₂, x₃, x₄, x₅, , а небазисными -x₁, x₆, . Это и означает переход к новой вершине многогранника допустимых решений. Чтобы найти значения координат нового допустимого базисного решения x⁰⁰ нужно строить новую симплекс-таблицу и провести в ней элементарные преобразования:

а) все элементы ведущей строки поделить на ведущий элемент, превратив этим самым ведущий элемент в 1 (для простоты выкладок);  
б) с помощью ведущего элемента (равного 1) все элементы ведущего столбика превратить в нули (аналогично методу исключения неизвестных);

В результате в  нулевом столбце получены значения новых базисных переменных x₂, x₃, x₄, x₅, (см. таблицу 2) - базисные компоненты новой вершины x⁰⁰ (небазисные компоненты x₁=0, x₆=0, ).