Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Завдання 5 Розв’язати задачу цілочислового програмування



Розв’язання

Зведемо ЗЛП до канонічного вигляду, помноживши перше рівняння на –1.

Оскільки в рівняннях обмежень відсутні базисні змінні, то введемо штучні базисні змінні , і розв’яжемо М-задачу в симплекс-таблиці 17.

Таблиця 17– Симплекс-таблиця М-задачі

    с -1 -5 -3 М М  
хб сб xi x1 x2 х3 х4 x5 х6 Q
х5 М -1 7/3
x6 М -1 6/3
без М   -2 ∆'j
с М   ∆''j
х5 М -5/3 5/3 10/3 -1/3 1,5
х4 -3 2/3 1/3 -1/3 1/3  
без М   -6 -4 -1 ∆'j
с М   -5/3 5/3 10/3 -4/3 ∆''j
x3 -5 1,5 -0,5 0,5 0,3 -0,1  
х4 -3 2,5 0,5 0,5 0,1 0,3  
без М f -15 -1 -3 -1,8 -0,4 ∆'j
с М   -1 -1 ∆''j

Оскільки , то отриманий план ЗЛП: не цілочисловий. Застосуємо метод Гоморі і знайдемо розв’язання ЗЦП.

Складемо правильне відсікання

.

Оскільки , то для побудови відсікання можна взяти будь-який рядок, наприклад, другий.

Одержимо

Додамо це обмеження новим рядком до симплекс-таблиці 18.

Оскільки Dj , то отриманий план: , оптимальний, цілочисловий,

Таблиця 18– Симплекс-таблиця

      -1 -5 -3  
Хб Сб Xі X1 X2 X3 X4 X5 Q
x3 -5 1,5 -0,5 0,5  
х4 -3 2,5 0,5 0,5 0,5
х5 -0,5 -0,5 -0,5
f = -1,5 -1 -3 Dj
x3 -5 -1  
х4 -3  
x1 -2  
f = -14 -2 -2 Dj

 

Зауваження.Якщо розв’язувати З.Ц.П. на максимум функції мети f, тоді штучні базисні змінні додаються до функції мети з коефіцієнтами – М.




4 ПИТАННЯ ДО ІСПИТУ(ЗАЛІКУ)

 

1. Задачі, що приводять до поняття математичного програмування.

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

3. Загальна задача лінійного програмування (З.3.Л.П.).

4. Властивості розв’язання 3.Л.П..

5. Графічний метод розв’язання 3.Л.П..

6. Симплексний метод розв’язання 3.Л.П..

7. Побудова опорних планів 3.Л.П..

8. Умови оптимальності опорного плану 3.Л.П..

9. Алгоритм симплексного методу.

10. Метод штучного базису.

11. Двоїсті задачі лінійного програмування. Економічна інтерпретація цих задач та їхніх розв’язків.

12. Види двоїстих задач. Теореми подвійності.

13. Постановка транспортної задачі (Т.3.).

14. Математична модель Т.3..

15. Умова збалансованості Т.3..

16. Зв'язок Т.3. із задачею лінійного програмування (3.Л.П.).

17. Визначення розв’язання (плану) Т.3..

18. Умова можливості розв'язання Т.3..

19. Визначення опорного плану Т.3..

20. Виродженість і невиродженість опорного плану.

21. Зв'язок виродженості й невиродженості опорного плану Т.3. із заповнюванням таблиці Т.3..

22. Визначення циклу в таблиці Т.3..

23. Зв'язок опорного плану Т.3. з циклічністю.

24. Метод північно-західного кута для визначення початкового опорного плану.

25. Метод мінімального елемента.

26. Метод Фогеля.

27. Суть методу потенціалів.

28. Вимоги до опорності плану при застосуванні методу потенціалів.

29. Постановка задачі про призначення.

30. Математична модель задачі про призначення.

31. Задача про призначення як різновид Т.3. зі своєю специфікою.

32. Розв’зання (план) задачі про призначення.

33. Теорема 1 про мінімізацію функціонала.

34. Теорема 2 (Фробеніуса).



35. Застосування теорем 1 і 2 для занулення матриці С.

36. Визначення «незалежного» нуля в матриці С.

37. Зв'язок “незалежних” нулів з оптимальністю плану задачі про призначення.

38. Суть угорського методу при розв’язанні задачі про призначення.

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

40. Постановка задачі цілочислового програмування (З.Ц.П.).

41. Математична модель З.Ц.П..

42. Зв'язок розв’язання З.Ц.П. з розв’язанням З.Л.П..

43. Способи розв’язання З.Ц.П..

44. Розв’язання З.Ц.П. методами «відсікання», поняття «правильного» відсікання.

45. Геометрична ілюстрація методу «відсікання».

46. Метод Гоморі, побудова «правильного» відсікання.

47. Алгоритм методу Гоморі.

 


СПИСОК ЛІТЕРАТУРИ

 

Основна література

1. Акулич И.Л. Математическое программирование в примерах и задачах.– М.: Высшая школа, 1986. –336 с.

2. Ашманов С.А. Линейное программирование. – М.: Наука, 1981. –289 с.

3. Кузнецов Ю.Н, Кузубов В.И., Волошенко А.Б. Математи­ческое программирование. – М.: Высшая школа, 1980. –331с.

4. Кузнецов А.В., Новикова Г.И., Холод Н.И. Сборник задач по математическому программированию. –Минск: Вышейшая школа, 1985. –

403 с.

5. Карманов В.Д. Математическое программирование.–М.: Высшая школа, 1980. –257 с.

Додаткова література

6. Сакович В.А. Исследование операций (детерминированные методы и модели). – Минск: Вышейшая школа, 1984. –296 с.

7. Черніченко В.Є. Навчальний посібник для практичних занять і контрольних робіт з дисципліни “Математичне програмування” для студентів денної та заочної форм навчання зі всіх спеціальностей економічного факультету та факультету менеджменту.– Кременчук: КДПУ, 2003. –33 с.

8. Черніченко В.Є. Навчальний посібник з дисципліни “Математичне програмування” на теми “Транспортна задача”, “Задача про призначення”, “Цілочислове програмування” для студентів денної та заочної форм навчання зі всіх спеціальностей факультетів економічного та управління (частина II).– Кременчук: КДПУ, 2005. –37 с.

9. Черніченко В.Є. Методичні вказівки щодо проведення лабораторної роботи з навчальної дисципліни “Математичне програмування” з теми “Нелінійне програмування. Квадратичне програмування ” для студентів денної та заочної форм навчання з усіх спеціальностей факультетів економічного та управління.– Кременчук: КДПУ, 2006. –15 с.

Додаток А

Зразок оформлення титульної сторінки семестрових практичних завдань

 

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

КРЕМЕНЧУЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ МИХАЙЛА ОСТРОГРАДСЬКОГО

 

 

кафедра ЕКОНОМІКИ

ШИФР (НОМЕР ЗАЛІКОВОЇ КНИЖКИ)

 

 


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!