5.1.2 Другий змістовний модуль

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

41. Дайте постановку загальної задачі цілочислового програмування та поясніть, у чому полягають труднощі її рішення.

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

43. Чим задача повністю цілочислового програмування відрізняється від задачі частково цілочислового програмування ?

44. Чому при рішенні задач цілочислового програмування є невиправданим округлення змінних оптимального рішення задачі без накладання умов цілочисловості ?

45. Дайте графічну інтерпретацію задачі цілочислового програмування.

Методи рішення задач цілочислового програмування.

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

47. Поясніть сутність методів відтинання та методів повернення для рішення задач цілочислового програмування.

48. Викладіть область застосування та послідовність дій у першому алгоритмі Гоморі.

49. Викладіть область застосування та послідовність дій у другому алгоритмі Гоморі.

50. Викладіть послідовність дій при рішенні задачі цілочислового програмування методом “відгалужень і меж”.

51. Дайте формулювання задачі про призначення та її математичну постановку. Поясніть, чому для її рішення неефективно використовувати симплекс-метод.

52. Угорський алгоритм рішення задачі про призначення.

53. Рішення задачі про призначення методом Мака.

54. Дайте формулювання та математичну постановку задачі про комівояжера.

55. Викладіть алгоритм рішення задачі про комівояжера методом “відгалужень і меж”.