- •2. Различные формы записи злп (общая, каноническая, симметрическая)
- •3. Геометрическая интерпретация целевой функции и ограничения злп. Геометрическая формулировка злп.
- •4. Графический метод решения злп.
- •5. Опорные планы злп. Соответствие между опорными планами и вершинами многогранника планов.
- •6. Основная теорема лп. Принципиальная схема решения злп, вытекающая из этой теоремы.
- •7. Симплексный метод решения злп. Общая идея симплекс-метода.
- •8. Признак оптимальности опорного плана злп.
- •9. Нахождение начального опорного плана злп.
- •10. Нахождение оптимального опорного плана злп.
- •11. Признак неограниченности целевой функции на множестве планов и геометрическая иллюстрация.
- •12. Признак бесконечности множества оптимальных планов и геометрическая иллюстрация.
- •13. Признак неразрешимости злп и геометрическая иллюстрация.
- •14. Алгоритм симплекс-метода.
- •15. Понятие двойственности в лп. Симметричные двойственные задачи и их экономическая интерпретация.
- •16. Несимметричные двойственные задачи. Связь между элементами моделей задач двойственной пары. Соответствие между переменными двойственных задач.
- •17.Теорема двойственности. Нах оптим плана двойств задачи по решению прямой
- •18.Теорема об оценках и ее эконом.Интерпритация.
- •20.Формул-ка и матем.Модель трансп. Задачи(тз) по критерию ст-ти. Особ-ти модели как злп.
- •21. Тз с открытой и закрытой моделью. Преобразование открытой модели в закрытую модель.
- •23. Теорема о ранге матрицы системы ограничительных уравнений тз и ее прикладное значение.
- •24. Циклы в транспортной таблице. Свойства циклов.
- •25. Способы построения нач опорного плана тз (Наимен Эл-та, северо-зап угла, Фогеля)
- •29. Потенциалы поставщиков и потр-лей, их вычисление и экон. Смысл.
- •30.Связь между оценками св клеток и потенциалами.
- •31. Алгоритм метода потенциалов.
- •34. 1Ая теорема двойственности.
- •35. 2Ая теорема двойств-ти и ее экон. Интерпритация.
- •36. Теорема о сущ-ии плана трансп задачи.
- •38. Теорема о ранге матрицы тз.
- •39. Алгоритм построения начального опорного плана злп.
- •40. Алгоритм построения оптимального опорного плана злп.
- •43. Вырожденность и ее устранение при решении задач симплекс-методом.
- •44. Признак бесконечности множества оптимальных планов и геометрическая иллюстрация.
- •46.Постановка и математич модель зцлп.
- •47.Алгоритм метода Гомори.
- •48.Метод ветвей и границ решения целочисленных задач.
- •49.Понятие о динамич прог. Особ-ти реш-я задач.
- •50. Задача о выборе кратчайшего пути по сети дорог и реш-е ее методом динамич прог.
- •51. Задача об оптим распред-ии ср-в м/у предпр-ями на расшир-е пр-ва и реш-е ее методом динамич прог.
- •53.Постановка задачи нлп. Трудности, возник при реш-ии задач нлп. Понятие выпуклой и вогнутой функции.
- •54. Графич метод реш-я задач нлп.
- •55.Метод Лагранжа решения задач нлп.
- •56. Градиентный метод реш-я задач нлп.
- •57. Метод искусств базиса реш-я задач лп симплекс методом.
18.Теорема об оценках и ее эконом.Интерпритация.
Теорема (об оценках): двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена, соотв.ограничения двойственной задачи.
yi*= Δf max /Δ bi i=1, m или yi*=(f max)’ bi
Δ f max = Δbi yi*
если Δ bi=1, то Δf max = yi* следовательно стоимост.оценка рес-са показ-т, как изменится выручка, если кол-во рес-са увелич-ся на 1 ед.
20.Формул-ка и матем.Модель трансп. Задачи(тз) по критерию ст-ти. Особ-ти модели как злп.
У m поставщиков А1, А2, …, Аm имеется a1, a2, …,am единиц однородного груза, к-рый д.б. доставлен n потребителям В1, В2, …, Вn в кол-вах b1, b2,…,bn. Известна стоимость(Cij) доставки ед-цы груза из пункта Ai в пункт Bj (j=от 1 до m). Необх-мо найти такой план транспорт-ки прод-ии при к-ром суммарные затраты минимальны. Обозначим ч/з xij объем перевозки груза из i-го пункта в j-ый (i=от 1 до m; j=от 1 до n). Тогда матрица X=(xij)m*n и есть план транспортировки груза Удельные трансп.издержки запис-ся в форме матрицы С=[cij]m *n и наз-ся она матрицей тарифов.
Экономико-матем.модель
ТЗ должна отражать все условия и цель
задачи в математич.форме. Переменные
xij(i=от
1 до m;j=от
1 до n)
должны удовлетворять ограничениям по
запасам, потребностям и условиям
неотрицательности:
(1)
xij>=0 (i=от 1 до m; j=от 1 до n)(2)
Цель ТЗ – минимизировать общие затраты на реализацию плана перевозок, к-рые можно представить функцией
f=c1.1 x1.1+c1.2 x1.2+…+c1.n x1.n+…+cm.1 xm.1+cm.2 xm.2+…+ cm.n xm.n =(i=от 1 до m)Σ(j=от 1 до n)Σcij xij. (3)
Математически ТЗ ставится так. Даны система ограничений (1) при условии (2) и линейная функция (3). Требуется среди множ-ва решений системы (1) найти такое неотрицат.решение, при к-ром линейная функция (3) принимает min значение. План перевозок X=(xij)m*n называется допустимым, если он удовлетворяет ограничениям (1) и (2). Допустимый план перевозок, доставляющий минимум целевой функции (3), наз-ся оптимальным.
Теорема: для того чтобы ТЗ имела допустимые планы, необходимо и достаточно выполнение равенства
(4)
Если равенство не выполняется, в задачу вводится фиктивный поставщик или потребитель. При > - фикт потр-ль, при < - фикт поставщик.
21. Тз с открытой и закрытой моделью. Преобразование открытой модели в закрытую модель.
Модель ТЗ наз-ют закрытой, если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т.е. выполняется равенство
(4) Если равенство не выполняется (< или >), то модель наз-ют открытой.
Для разрешимости ТЗ с открытой моделью необходимо преобразовать ее в закрытую. Так, при выполнении первого условия необходимо ввести фиктивный (n+1)-й пункт назначения Bn+1, т.е. в матрице задачи предусматривается дополнительный столбец. Спрос фиктивного потребителя
а все тарифы – одинаковыми, чаще всего равными нулю, т.е. C i,n+1=0 (i=от 1 до m). Аналогично при выполнении 2 условия вводится фиктивный поставщик, запас груза у которого равен
А тарифы дополнительной строки распределительной таблицы равны нулю, т.е. C m+1,j =0. (j=от 1 до n)
При преобразовании открытой задачи в закрытую целевая функция не меняется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю.
