Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Алгоритм розв’язання транспортної задачі

⇐ ПредыдущаяСтр 20 из 20

 

1. Вибір першого допустимого рішення – використовується метод мінімального елемента. У першу чергу заповняються клітинки з найменшими відстанями.

 

ТАБЛИЦЯ 1.

  A 12 т B 10 т C 6 т D 2 т
Львів 13 т.                
(2) - (6) 7 (8) 6 (4) -
Київ 17 т.                
(1) 12 (5) 3 (7) - (3) 2
                     

 

Послідовність заповнення таблиці за методом мінімального елемента (у дужках в таблиці зазначено послідовність кроків виконання):

1. найменша відстань у клітинці а21, тому заповнюємо найперше її. Проставляємо туди таке число, щоб по можливості максимально задовольнити вимогу відповідного покупця (у нашому випадку – А), а21 = 12.

2. попит гуртівні А задоволений повністю, тому в клітинці а11 пусто.

3. серед інших найменша відстань 21 у клітинці а24, тому ставимо туди 2.

4. попит D задоволений, тому у клітинці а14 пусто.

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

17 – (12 + 2) = 3.

6. заповняємо клітинку угорі а12: 10 – 3 =7.

7. у 2-му ряді залишилась клітинка а23 – запаси повністю вичерпані, тому там пусто.

8. остання клітинка а13 = 6.

 

2. Перевірка на оптимальність.

Знайдено перший допустимий план перевезень, але він не обов’язково мусить бути оптимальним. Для перевірки плану на оптимальність треба ввести m + n додаткових величин, які називають потенціалами.

 

ТАБЛИЦЯ 2.

  A 12 т B 10 т C 6 т D 2 т Um
Львів 13 т.                 U1 = 0
-     -
Київ 17 т.                 U2 = –4
    -  
Vn V1 = 20 V2 = 26 V3 = 28 V4 = 25  

 

Потенціали визначаються так:

1. Для початку U1 = 0 (у всіх випадках).

2. Сума потенціалів рядка та стовпчика має дорівнювати відстані (тарифу) – це числа на сірому фоні. Повинна виконуватися рівність Cmn = Um + Vn. Спочатку визначається потенціал, що відповідає непорожній клітинці рядка 1. Можна взяти 2-ий стовпчик і визначити V2. V2 = 26 – 0 = 26.

3. Далі розраховуємо потенціал для 3-го стовпчика: V3 = 28 – 0 = 28.

4. Тепер розрахуємо потенціал 2-го рядка за допомогою клітинки а22: U2 = 22 –26 = –4.

5. Можна визначити потенціал 1-го стовпчика: V1 = 16 – (–4) = 20.

6. Залишився останній потенціал 4-го стовпчика: V4 = 21 – (–4) = 25.

 

Кожна пуста клітинка перевіряється. Для цього з тарифу пустої клітинки віднімається сума потенціалів рядка і стовпчика, або amn = Cmn – (Um + Vn).

1. amn = Cmn – (Um + Vn) = a11 = C11 – (U1 + V1) = 17 – (20 + 0) = –3;

2. a14 = C14 – (U1 + V4) = 27 – (25 + 0) = 2;

3. a23 = C23 – (U2 + V3) = 26 – (28 – 4) = 2.

Якщо серед результатів є від’ємні, то знайдений план не є оптимальним і треба зробити перепланування.

 

3. Перепланування.

Серед порожніх клітинок з від’ємним значенням різниці потенціалів вибирається та, у якої різниця amn є найменшою. Ця клітинка рекомендується до заповнення. У нашому випадку це буде клітинка а11. Ця клітинка стає ненульовою, тобто в неї потрібно вписати число.

 

Методика перепланування така. В межах таблиці будується прямокутник, одна з вершин якого припадає на дану клітинку (а11), а інші мусять попасти на заповнені клітинки

 

ТАБЛИЦЯ 3.

  A 12 т B 10 т C 6 т D 2 т
Львів 13 т.                
-     -
Київ 17 т.                
    -  

 

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

 

У нашій задачі сусідніми до а11 будуть а12 та а21. Серед них менше значення в а12 = 7. Тому число 7 треба вирахувати з а12 і занести в а11. Для того, щоб сума у стовпчику 1 залишалась 12 треба від а21 відняти 7. а21 = 12 – 7 = 5. Тепер, щоб вирівняти суму в рядку 2 необхідно це число 7 додати у клітинку а22: 3 + 7 = 0 (див. таблицю 4)


 

ТАБЛИЦЯ 4.

  A 12 т B 10 т C 6 т D 2 т
Львів 13 т.                
  -   -
Київ 17 т.                
    -  

 

Знайдено новий допустимий план перевезень і його знову треба перевірити на оптимальність.

 

4. Перевірка на оптимальність.

Розраховуються потенціали (таблиця 5). Методика розрахунку наведена у пункті 2.

 

ТАБЛИЦЯ 5.

  A 12 т B 10 т C 6 т D 2 т Um
Львів 13 т.                 U1 = 0
  -   -
Київ 17 т.                 U2 = –1
    -  
Vn V1 = 17 V2 = 23 V3 = 28 V4 = 22  

 

Перевіряємо пусті клітинки:

1. amn = Cmn – (Um + Vn) = a12 = C12 – (U1 + V2) = 26 – (23 + 0) = 3;

2. a14 = C14 – (U1 + V4) = 27 – (22 + 0) = 5;

3. a23 = C23 – (U2 + V3) = 26 – (28 – 1) = –1.

Є від’ємний елемент, тому необхідне перепланування.

 

5. Перепланування.

Будуємо прямокутник по клітинках, однією з вершин є клітинка з мінімальним amn – це клітинка а23, а інші вершини мають лежати на заповнених клітинках (а11, а21 та а13).

 

ТАБЛИЦЯ 6.

  A 12 т B 10 т C 6 т D 2 т
Львів 13 т.                
  -   -
Київ 17 т.                
    -  

 

У порожню клітинку а23 треба внести додатнє значення. Серед сусідніх до а23 вершин прямокутника (а21 та а13) менше значення має а21 = 5, тому 5 треба внести в а23. Далі необхідно скоректувати значення так, щоб суми в рядках та стовпцях не змінилися. Нова таблиця буде виглядати так:

 

ТАБЛИЦЯ 7.

  A 12 т B 10 т C 6 т D 2 т
Львів 13 т.                
  -   -
Київ 17 т.                
-      

 

6. Перевірка на оптимальність.

Розраховуємо потенціали за відомою методикою.

 

ТАБЛИЦЯ 8.

  A 12 т B 10 т C 6 т D 2 т Um
Львів 13 т.                 U1 = 0
  -   -
Київ 17 т.                 U2 = –2
-      
Vn V1 = 17 V2 = 24 V3 = 28 V4 = 23  

 

Перевіряємо пусті клітинки:

1. amn = Cmn – (Um + Vn) = a12 = C12 – (U1 + V2) = 26 – (24 + 0) = 2;

2. a14 = C14 – (U1 + V4) = 27 – (23 + 0) = 4;

3. a21 = C21 – (U2 + V1) = 16 – (17 – 2) = 1.

Від’ємних елементів немає, тому план є оптимальним.


 

min f = 12×17 + 1×28 + 10×22 + 5×26 + 2×21 = 624 або 62400 тонно-кілометрів.×

Завдання до виконання:

Завдання потрібно обрати за номером студента в журналі групи.

 

Задача 1.

Знайти розв’язок задачі лінійного програмування, якщо її економіко-математична модель подана таблицею:

1. використовуючи геометричну інтерпретацію;

 

Варіант 1 fmax= x1 + 2x2   Варіант 2 fmax= x1 – 2x2   Варіант 3 fmax= - 2x1 + x2  
4x1 - 2x2 ≤12   4x1 - 2x2 ≤12   4x1 - 2x2 ≤12  
- x1 + 3x2 ≤6   - x1 + 3x2 ≤6   - x1 + 3x2 ≤6  
2x1 + 4x2 ≥16   2x1 + 4x2 ≥16   2x1 + 4x2 ≥16  
x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.  
Варіант 4 fmax= x1 + 2x2   Варіант 5 fmax= x1 – 2x2   Варіант 6 fmax= - 2x1 + x2  
4x1 – 3x2 ≤12   4x1 - 3x2 ≤12   4x1 – 3x2 ≤12  
- x1 + 3x2 ≤6   - x1 + 3x2 ≤6   - x1 + 3x2 ≤6  
2x1 + 4x2 ≥8   2x1 + 4x2 ≥8   2x1 + 4x2 ≥8  
x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.  
Варіант 7 fmax= 2x1 + 3x2   Варіант 8 fmax= 2x1 + 3x2   Варіант 9 fmax= 2x1 + 3x2  
2x1 + x2 ≤10   2x1 + x2 ≤8   2x1 + x2 ≤6  
- 2x1 + 3x2 ≤6   - 2x1 + 3x2 ≤6   - 2x1 + 3x2 ≤6  
2x1 + 4x2 ≥8   2x1 + 4x2 ≥8   2x1 + 4x2 ≥8  
x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.  
Варіант 10 fmax= 2x1 - 3x2   Варіант 11 fmax= - 2x1 + 3x2   Варіант 12 fmax= 2x1 + 3x2  
2x1 + x2 ≤6   2x1 + x2 ≤10   2x1 + x2 ≤10  
- 2x1 + 3x2 ≤6   - 6x1 + 3x2 ≤6   - 3x1 + 3x2 ≤6  
2x1 + 4x2 ≥8   2x1 + 4x2 ≥16   2x1 + 4x2 ≥8  
x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.  
Варіант 13 fmax= 2x1 – 3x2   Варіант 14 fmіn= 2x1 – 3x2   Варіант 15 fmin= - 2x1 – 3x2  
2x1 + x2 ≤10   2x1 + x2 ≤10   2x1 + x2 ≤10  
- 3x1 + 3x2 ≤6   - 3x1 + 3x2 ≤6   - 3x1 + 3x2 ≤6  
x1 + 2x2 ≥8   x1 + 2x2 ≥8   x1 + 2x2 ≥8  
x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.  
Варіант 16 fmax= 2x1 + x2   Варіант 17 fmin= - 2x1 – 3x2   Варіант 18 fmin= - 2x1 + x2  
2x1 + x2 ≤10   2x1 + x2 ≤10   3x1 – 2x2 ≤12  
- 6x1 + 3x2 ≤6   - 6x1 + 3x2 ≤6   - x1 + 2x2 ≤8  
x1 + x2 ≥5   x1 + x2 ≥5   x1 + x2 ≥6  
x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.  
Варіант 19 fmax= x1 + 2x2   Варіант 20 fmax= 2x1 – 2x2   Варіант 21 fmax= - x1 – 2x2  
3x1 - 2x2 ≤12   3x1 - 2x2 ≤12   3x1 - 2x2 ≤12  
- x1 + 2x2 ≤8   - x1 + 3x2 ≤6   - x1 + 3x2 ≤6  
x1 + x2 ≥6   x1 + x2 ≥6   x1 + x2 ≥6  
x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.  
Варіант 22 fmin= x1 - x2   Варіант 23 fmax= x1 + 2x2   Варіант 24 fmax= - x1 +2x2  
3x1 - 2x2 ≤12   3x1 - 2x2 ≤12   3x1 - 2x2 ≤12  
- x1 + 2x2 ≤8   - x1 + 3x2 ≤6   - x1 + 3x2 ≤6  
x1 + x2 ≥7   x1 + x2 ≥6   x1 + x2 ≥6  
x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.  
Варіант 25 fmin= - x1 + 2x2   Варіант 26 fmin= 2x1 + x2   Варіант 27 fmin= - x1 – 3x2  
4x1 – 2x2 ≤12   4x1 - 2x2 ≤12   4x1 - 2x2 ≤12  
- x1 + 3x2 ≤6   - x1 + 3x2 ≤6   - x1 + 3x2 ≤6  
2x1 + 4x2 ≥12   2x1 + 4x2 ≥12   2x1 + 4x2 ≥12  
x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.  
Варіант 28 fmin= - 2x1 - x2   Варіант 29 fmin= x1 – 2x2   Варіант 30 fmin= - 4x1 + x2  
4x1 – 3x2 ≤12   4x1 - 3x2 ≤12   4x1 – 3x2 ≤12  
- x1 + 3x2 ≤6   - x1 + 3x2 ≤6   - x1 + 3x2 ≤6  
2x1 + 4x2 ≥8   2x1 + 4x2 ≥8   2x1 + 4x2 ≥8  
x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.   x1≥ 0; x2 ≥ 0.  

 


Задача 2.

Знайти розв’язок транспортної задачі.

В m пунктах виробництва А1, А2, …, Аm знаходиться однорідний товар в кількості а1, а2, …, аm одиниць, який повинен бути доставлений до n користувачів В1, В2, …, Вn в кількостях в1, в2, …, вn. Відомі витрати на транспонтування одиниці товару із Аi в Вj. Скласти план перевезень, при якому забезпечувалися потреби і витрати на перевезення булі б мінімальні.

1. склавши початковий план методом:

        • мінімального елемента;

· знайти оптимальний план методом потенціалів до початкового плану складеного методом мінімального елемента.

 

Варіант 4   В1 В2 В3 В4     Варіант 5   В1 В2 В3 В4     Варіант 6   В1 В2 В3 В4  
А1           А1           А1          
А2           А2           А2          
А3           А3           А3          
                                   

 

Варіант 7   В1 В2 В3     Варіант 8   В1 В2 В3     Варіант 9   В1 В2 В3  
А1         А1         А1        
А2         А2         А2        
А3         А3         А3        
А4         А4         А4        
                             

 

Варіант 10   В1 В2 В3     Варіант 11   В1 В2 В3     Варіант 12   В1 В2 В3  
А1         А1         А1        
А2         А2         А2        
А3         А3         А3        
А4         А4         А4        
                             

 

 

Варіант 13   В1 В2 В3 В4     Варіант 14   В1 В2 В3 В4     Варіант 15   В1 В2 В3 В4  
А1           А1           А1          
А2           А2           А2          
А3           А3           А3          
                                   

 

 

Варіант 16   В1 В2 В3 В4     Варіант 17   В1 В2 В3 В4     Варіант 18   В1 В2 В3 В4  
А1           А1           А1          
А2           А2           А2          
А3           А3           А3          
                                   

 

 

Варіант 19   В1 В2 В3     Варіант 20   В1 В2 В3     Варіант 21   В1 В2 В3  
А1         А1         А1        
А2         А2         А2        
А3         А3         А3        
А4         А4         А4        
                             

 

 

Варіант 22   В1 В2 В3     Варіант 23   В1 В2 В3     Варіант 24   В1 В2 В3  
А1         А1         А1        
А2         А2         А2        
А3         А3         А3        
А4         А4         А4        
                             

 

 

Варіант 25   В1 В2 В3 В4     Варіант 26   В1 В2 В3 В4     Варіант 27   В1 В2 В3 В4  
А1           А1           А1          
А2           А2           А2          
А3           А3           А3          
                                   

 

 

Варіант 28   В1 В2 В3 В4     Варіант 29   В1 В2 В3 В4     Варіант 30   В1 В2 В3 В4  
А1           А1           А1          
А2           А2           А2          
А3           А3           А3          
                                   

 

 

Контрольні запитання:

1. Предмет дисципліни “Математичне програмування”.

2. Загальна постановка задачі математичного програмування.

3. Задача лінійного програмування

4. Математичний запис загальної задачі лінійного програмування.

5. Розв'язання задачі лінійного програмування на основі її геометричної інтерпретації. Основні етапи методу.

6. Економічна постановка транспортної задачі.

7. Математична постановка транспортної задачі


Література:

 

  1. Міхайленко В.М., Федоренко Н.Д. Алгебра та геометрія для економістів. — К.: 2000.
  2. И.И.Валуцэ, Г.Д. Дилигул. Математика для техникумов.Москва. «Наука», 1989г.
  3. Вища математика. П.П. Овчінніков та ін. Ч.1.Київ «Техніка», 2003р.
  4. А.М. Самойленко, С.А. Кривошея, А.М. Самойленко, С.А. Кривошея, Н.А. Перестюк. Дифференциальные уравнения. Примеры и задачи.-Москва, «Высшая школа», 1989г.
  5. П.Е.Данко, А.Г.Попов, Т.Я. Кожевникова. Высшая математика в упражнениях и задачах.-Москва «Высшая школа», 1980г.
  6. Л.І.Дюженкова, Т.В.Колесник, М.Я. Ляшенко, Г.О.Михалін, М.І.Шкіль, Математичний аналіз у задачах і прикладах. В 2 частинах.-Київ, «Вища школа»,2003р.
  7. Навчально – методичні матеріали до виконання контрольних робіт з вищої математики. Ч.1 / Грижук О.П. та ін. – Черкаси, ЧДТУ, 2004 р.

⇐ Предыдущая11121314151617181920





Date: 2015-10-19; view: 365; Нарушение авторских прав


mydocx.ru - 2015-2024 year. (0.038 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию