Математическое программирование

Автор работы: Пользователь скрыл имя, 18 Декабря 2012 в 22:24, контрольная работа

Краткое описание

Фірма для автомобільної промисловості виготовляє деталі двох типів А і В. Для їх виготовлення фірма має фонд робочого часу 4000 годин на тиждень. Для виготовлення однієї деталі типу А потрібно використати одну год., а типу В – 2 години. Потужність фірми дозволяє виготовити деталей типу А максимум 2250 од., а типу В - 1750 од. за тиждень. Кожна деталь типу А потребує 2 кг металевих стрижнів та 5 кг листового прокату, а для виготовлення деталі типу В потрібно 5 кг металевих стрижнів та 2 кг листового прокату.

Прикрепленные файлы: 1 файл

Мат. програм., Яна..doc

— 232.50 Кб (Скачать документ)

 

З даної таблиці  знаходимо вираз для вільної  змінної и3:

и3 = - и1 – 7и2 – v 2 + 50

та із подальшого розгляду виключаємо другий стовпець.

   Табл. 4.3 не містить опорного розв'язку, бо в стовпці вільних елементів є від'ємні. Для його знаходження проглядаємо другий рядок із від'ємним вільним, склавши невід'ємні відношення вільних елементів до відповідних елементів першого стовпця, бачимо, що найменше відношення утворене із елементом – 3.

  З цим елементом здійснюємо крок МЖВ і отримуємо табл. 4.4.

 

Таблиця 4.4.

 

VI =

У3 =

У4 =

\\> =

 

- х2

- х3

- х4

1

И1

У1 =

5/3

-31/3

  - 10

- 49

И2

У2 =

-23/3

13/3

- 3

-15

V1

 Х1 =

-1/3

5/3

1

8

1

z =

130/3

-50/3

15

160


 

     Аналогічно попередньому із елементом а13 здійснюємо наступний крок МЖВ і одержуємо табл. 4.5.

Таблиця 4.5.

   

У3 =

И1 =

У2

 

- х2

3

- у1

1

V1

Х4 =

-1/6

31/30

-1/10

-49/10

и2

У2 =

-49/6

223/30

3/10

-3/10

VI

Х1=

-1/6

19/30

1/10

31/10

1

 z

275/6

193/6

3/2

173/2


Далі, здійснивши крок МЖВ з елементом а 23 = - 3/10,

остаточно маємо табл. 53.

Таблиця 4.6.

 

V 2 =

V 3 =

и2 =

 W =

 

2

3

- у2

1

V4

Х4 =

     

5

И1

У =

     

1

V1

Х1=

     

3

1

z =

5

209/3

5

85


В останній таблиці наявність додатних вільних елементів та додатних коефіцієнтів 2 -рядка про те, що опорний розв'язок знайдено, і цей розв'язок є оптимальним для цільової функції.

Із табл. 4.6. знаходимо розв'язок прямої задачі:

W мах = 85 х  (х2  - х3 = У2 = 0, х1 = 3,   х4 =5,  у1 = 1)

та спряженої  задачі:

W мін = 85 (и1 = V1 = V4 = 0,     V2 = 5,   V3 = 208/3,     и2 = 5).

 

 

5. Транспортна  задача.

   Знайти оптимальний розв'язок транспортної задачі за критерієм мінімальних сукупних витрат за перевезення, якщо вектор запасу вантажу в пунктах постачання А = {1ОО; 15О; 2ОО; 25О},  вектор потреб

В- {12О;8О;2ОО} та матриця тарифів перевезень

             10       5         3

              8        10       6

С =        4         9         2

             11        5         2

Розв'язування:

     Перевіряємо умову балансову : Σаі = Σві.

Σаі =100+150+200+250=700,

 Σві=120 + 80+200 = 400.

    Як бачимо, балансову умову не виконано - «потреб» менше ніж «можливостей» постачальників. Вводимо «фіктивного» споживача з потребами 700-400=300 одиниць з нульовим тарифом за перевезення.

    З врахуванням фіктивного споживача дані «закритої моделі» задачі записуємо в транспортну таблицю, в якій знаходимо опорний розв'язок методом подвійних відміток, оптимальність якого перевіряємо методом потенціалів.

Таблиця  5.

 

120

80

200

300

 

100

 

30

 

70

0

150

     

150

0

200

 

120

   

80

0

250

 

 

50

 

200

0

0

vJ

4

5

2

0

 

 

 

Як   бачимо,    знайдений    опорний    розв'язок   з    матрицею перевезень

 

                        0      30        0       70

        Хіj =        0       0         0      150

                      120     0         0        80

                        0      50       200      0 

   задовольняє умови потенціальності, що означає його оптимальність. При цьому найменша вартість перевезень складає:

Qмін = 30 - 5 + 120 - 4 + 50 - 5 + 200 - 2 = 1280 грн.

   Відповідь: 1280 грн. 

 

 

 

 

 

 

 

 

 

 

 

   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

 

 


 

 

 



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