Системное програмирование

Автор: Пользователь скрыл имя, 20 Января 2012 в 22:34, контрольная работа

Описание работы

Компьютерный эксперимент. Анализ результатов моделирования. Двойственный симплекс-метод. Содержательные и формальные модели. Содержательная классификация моделей. Прямая и двойственная задачи. Связь между решениями прямой и двойственной задачами. Этапы моделирования. Постановка задачи. Разработка модели. Жесткие и мягкие модели. Универсальность моделей. Прямая и обратная задачи математического моделирования.

Работа содержит 1 файл

ответы.docx

— 804.28 Кб (Скачать)

таблица 8

Пункты

Отправления

Пункты  назначения Запасы
В1 В2 В3 В4
А1 1

30

  2    —

       20

|— 4| 1     +

       3

 
50
А2 2

       0

3        +

        10

 1

10

5     — 

       10

 
30
А3 3

       -2

2

        0

4

       -4

4

     10

 
10
Потребности 30 30 10 20 90
 

числу 10, стоящему в плюсовой клетке табл. 8, добавим 10 и вычтем 10 из числа 20, находящегося в минусовой  клетке табл. 8. Клетка на пересечении строки А2 и столбца В4 становится свободной.

  После этих преобразований получаем новый опорный план (табл. 9).

таблица 9

Пункты

Отправления

Пункты  назначения Запасы

 

В1 В2 В3 В4
А1 1

      30

2      -

      10

4     -2 1    +

10

 
50
А2
2

0

3

20

1

10

5

    -3

 
30
А3 3

    +1

2       +

   +3

4

     -1

4        -

10

 
10
Потребности 30 30 10 20 90

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

b1 - a1 = 1,  b2 - a1 = 2,  b4 - a1 = 1,

b2- a2 = 3,  b3 - a2 = 1,  b4 - a3 = 4,

Полагаем a1 =0, получаем b1 = b4 = l, b2 = 2, a2=-1, b3= 0, a3= -3. Для каждой свободной клетки вычисляем число aij ; имеем, a13= -2, a21 = 0, a24 = -3, a32= 3, a 31= 1, a33 = -1.

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

  таблица 10

Пункты

отправления

Пункты  назначения Запасы
В1 В2 В3 В4
А1 1

30

2

0

4      -4 1

20

 
50
A2 2    

        0

3

20

1

10

5   

    -3

 
30
А3 3     

      -2

2

10

4

    -4

4

     -3

 
10
Потребности 30 30 10 20 90

  Сравнивая разности bj - ai новых потенциалов, отвечающих свободным клеткам табл. 2.10, с соответствующими числами сij, видим, что указанные разности потенциалов для всех свободных клеток не превосходят соответствующих чисел сij . Следовательно, полученный план

является  оптимальным. При данном плане стоимость  перевозок S = 1*30 + 2*0+1*20 + 3*20+1*10 + 2*10 = 140.  
 
 

Вариант 2.

Постановка  транспортной задачи. Нахождение опорного плана транспортной задачи.

Постановка  задачи и ее решение

Пример 1

Фирма должна отправить некоторое количество кроватей с трех складов в пять магазинов. На складах имеется соответственно 15, 25, 20 кроватей, а для пяти магазинов  требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати (в долларах) со склада в магазин приведена в таблице. 

Склад Магазин
S1 S2 S3 S4 S5
W1

W2

W3

1

5

4

0

1

8

3

2

1

4

3

4

2

3

3

Как следует  спланировать перевозку кроватей для  минимизации стоимости? Пусть  количество кроватей, отправляемых со склада I в магазин j. Ясно, что , и в силу ограничений на возможности поставки со складов (предложение) и спрос в магазинах они удовлетворяют следующим условиям:

x11+x12+x13+x14+x15 = 15,

+ x21 +x22 +x23 +x24 +x25                                     = 25,

    + x31 +x32 +x33 +x34 + x35                                                                        = 20

(для  предложения);

x11 + x21 + x31 = 20,

x12 +x22 + x32 = 12,

x13 + x23 + x33 =  5,

х14 + x24 + x34 = 8,

x15 + x25 + x35 = 15

(для спроса). Стоимость, равная

F = х11 + 0x12 + 3х13 + 14 + 2x15 + 21 + ... + 4х34+ 3х35,

должна быть минимизирована при этих ограничениях.

  Эта задача является задачей линейного  программирования, но специального вида. В частности, коэффициенты в ограничениях принимают значения 0 или 1, а каждая переменная входит только в два ограничения. На первый взгляд может показаться, что ограничения в виде равенств, определяющих предложение, должны быть заменены на ограничения в виде неравенств со знаком £, а ограничения в виде равенств, определяющих спрос на ограничения в виде неравенств, со знаком ³. Однако, поскольку суммарный спрос равен сумме поставок, во всех случаях должно выполняться равенство. Заметим также, что сумма по первым трем ограничениям дает тот же результат, что и сумма по последним пяти ограничениям. Поскольку независимых ограничений только 7, а не 8, следовательно, базисное допустимое решение и оптимальное решение будет содержать 7 ненулевых значений .

Эти результаты обобщаются на транспортную задачу с  т пунктами производства и объемами производства (i = 1, 2, . . . , т ), и п пунктами потребления и объемами потребления (j =1,..., п), где

(1)

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

x11+x12+ …+x1n = a1,

                          x21 +…+ x2n                                     = a2,

…………………………………………………………………………………..

                   xm1 +…                  + xmn    = am,  (2)

x11 +x21 + xm1 = b1,

   x12 + x22 + xm2 = b2,

………………………………………………………………………………………………

x1n + x2n + xmn = bn 

и минимизирующих функцию

F=С11Х11 + С12Х12 +...+СтnХтп.

Короче, соотношения  (2) можно переписать так:

найти такие  , для которых справедливы неравенства

   (i=1,…,m), (3)

(j=1,…,n) (4)

и которые минимизируют функцию

 (5)

Поскольку согласно уравнению (1), имеется всего т + п - 1 независимых ограничений и, следовательно, т + п — 1 базисных переменных в базисном допустимом решении.

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

Переход к общему случаю очевиден.

  Представляя данные в таком виде, легко построить  первое базисное допустимое решение  задачи. Это можно сделать по правилу "самая дешевая продукция реализуется  первой". Поскольку задача состоит  в минимизации общей стоимости, находим наименьшую стоимость во всех клетках: 0 в строке 1, столбце  2 и присваиваем переменной х12 значение 12 (наименьшая из сумм по строке и по столбцу). Теперь столбец 2 можно удалить, уменьшив сумму по строке на 12, т. е. заменив ее на 3. Потом та же процедура применяется к полученному массиву.

Затем переменной х11 присваивается значение 3 (или переменной х33значение 5), удаляется строка 1, сумма по столбцу 1 заменяется на 17 и осуществляется переход к следующему массиву и т. д.

Информация о работе Системное програмирование