Subject

Линеарно програмирање

Course Title

Линеарно програмирање
Linear Programming

Code

m23_s_060

Study Programme

—

Organizer of the study programme (unit, institute, department or division)

Faculty of Computer Science and Engineering

Degree level (first, second, third cycle)

Second cycle

Academic year / semester

10 / Summer

Number of ECTS credits

Teacher

Методија Јанчески

Prerequisites for enrolling in the course

—

10.

Objectives of the course programme (competences)

Целта на курсот е студентите да се запознаат со математичката теорија на линеарното програмирање, со пресметувачките аспекти и најпопуларните практични примени на линеарното програмирање. По завршување на курсот кандидатите: ќе имаат продлабочени знаења за повеќе различни алгоритми на линеарното програмирање и ќе бидат оспособени за решавање на широк спектар задачи од областа на економските и техничките истражувања, од практиката на планирањето и организацијата на производство и од управување на системи поврзани со наоѓање најмала (или најголема) вредност на некоја функција од голем број на променливи.

11.

Course content

1. Елементи од теоријата на конвексни полиедри (конвексни множества, пар заемно-дуални системи линеарни равенки и неравенки, конвексни конуси, конвексни многустрани конуси, конвексни многустрани множества, конвексни полиедри)

2. Задача на линеарното програмирање (ЛП) (еквивалентна форма на ЛП задачата, допустлива област, екстремални програми, стандарден вид на ЛП-задача, базни програми, геометриска интерпретација на ЛП-задачата во Rn и Rm)

3. Симплекс метод (основни теореми на методот симплекс, симплекс алгоритам, наоѓање почетна базна програма, дегенерација и цикл, лексикографски облик на методот симплекс, модифициран симплекс алгоритам)

4. Дуалност во линеарното програмирање (дефиниција на пар заемно-дуални ЛП-задачи, основна теорема во дуалноста, функција на Лагранж за парот заемно-дуални ЛП-задачи, дуален симплекс алгоритам, наоѓање почетно дуално допустливо решение, економска интерпретација на парот заемно-дуални задачи, матрични игри и дуалност)

5. Специјални ЛП-задачи и методи (класична транспортна задача, правило на северозападниот агол, решение на класична транспортна задача, варијанти на транспортната задача, ЛП задача со блок-структура, постоптимални задачи, параметарски задачи)

6. Дискретно програмирање (примери на целобројни задачи, методи на отсекување, дискретен алгоритам, цикличен алгоритам, приближни методи, адитивен алгоритам, алгоритам на Белман)

12.

Learning methods

Предавања поддржани со презентации преку слајдови, интерактивни предавања, вежби, тимска работа, студии на случај, самостојна изработка и одбрана на проектна задача и семинарска работа. Покрај методот на усно излагање, ќе се применуваат активните методи на учење како: метод на проблемска настава, метод на проектна настава, метод на истражување, метод на самостојна работа и други.

13.

Total available time

6 ECTS x 30 hours = 180 hours

14.

Distribution of available time

50 + 30 + 20 + 40 + 40 = 180 часа

15.

Forms of teaching activities

15.1.	Lectures - theoretical instruction	50 часови
15.2.	Exercises (laboratory, auditory), seminars, teamwork	30 hours

16.

Other forms of activities

16.1.	Project assignments	40 hours
16.2.	Independent assignments	20 hours
16.3.	Home study	40 hours

17.

Assessment method

17.1.	Tests	20 бодови
17.2.	Seminar paper / project (presentation: written and oral)	40 бодови
17.3.	Activities and learning	10 бодови
17.4.	Final exam	50 бодови

18.

Grading criteria (points / grade)

up to 50 points	5 (five) (F)
from 51 to 60 points	6 (six) (E)
from 61 to 70 points	7 (seven) (D)
from 71 to 80 points	8 (eight) (C)
from 81 to 90 points	9 (nine) (B)
from 91 to 100 points	10 (ten) (A)

19.

Requirement for obtaining a signature and taking the final exam

—

20.

Language of instruction

македонски

21.

Method for monitoring the quality of teaching

internal evaluation and survey mechanism

22.

Literature

22.1.

Required literature

22.2.

Additional literature

No. Author Title Publisher Year