Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Математика Математика

Двойственный симплекс-метод и доказательство теоремы двойственности

Забавная пачка денег "100 долларов".
Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь внимательней, и Вы увидите
60 руб
Раздел: Прочее
Фонарь желаний бумажный, оранжевый.
В комплекте: фонарик, горелка. Оформление упаковки - 100% полностью на русском языке. Форма купола "перевёрнутая груша" как у
87 руб
Раздел: Небесные фонарики
Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение

ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ Кафедра математики КУРСОВАЯ на тему: Двойственный симплекс-метод и доказательство теоремы двойственности. Студент группы МЭК 1-1 - А.С. Кормаков Научный руководитель - Солодовников А.С. МОСКВА – 2001 Содержание 1. Двойственность в линейном программировании 3 2. Несимметричные двойственные задачи. Теорема двойственности. 4 3. Симметричные двойственные задачи 9 4. Виды математических моделей двойственных задач 11 5. Двойственный симплексный метод 12 6. Список используемой литературы 14 1. Двойственность в линейном программировании Понятие двойственности. С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется исходной. Связь исходной и двойственной задач состоит в том, что коэффициенты Cj функции цели исходной задачи являются свободными членами системы ограничений двойственной задачи, свободные члены Bi системы ограничений исходной задачи служат коэффициентами функции цели двойственной задачи, а матрица коэффициентов системы ограничений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи. Решение двойственной задачи может быть получено из решения исходной и наоборот. В качестве примера рассмотрим задачу использования ресурсов. Предприятие имеет т видов ресурсов в количестве bi (i = 1, 2, ., m) единиц, из которых производится видов продукций. Для производства 1 ед. i- й продукции расходуется aij ед. -гo ресурса, а ее стоимость составляет Cj ед. Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Обозначим через xj (j =1,2, ., ) количество ед. j-й продукций, Тогда исходную задачу сформулируем так. Найти вектор Х =(x1, x2, , x ), который удовлетворяет ограничениям a11x1 a12x2 a1 x ( b1, a21x1 a22x2 a2 x ( b2, xj ( 0 (j =1,2, ., ) am1x1 am2x2 am x ( bm, и доставляет максимальное значение линейной функции Z = C1x1 C2x2 C x , Оценим ресурсы, необходимые для изготовления продукции. За единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через уi (j =1,2, ., m) стоимость единицы i-го ресурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление единицы j-й продукции, равна . Стоимость затраченных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться неравенство ( Cj, j =1,2, ., . Стоимость всех имеющихся ресурсов выразится величиной . Итак, двойственную задачу можно сформулировать следующим образом. Найти вектор Y =(y1, y2, , y ), который удовлетворяет ограничениям a11y1 a12y2 am1ym ( C1, a12y1 a22y2 am2ym ( C2, yj ( 0 (i =1,2, ., m) a1 y1 a2 y2 am ym ( Cm, и доставляет минимальное значение линейной функции f = b1y1 b2y2 bmym. Рассмотренные исходная и двойственная задачи могут быть экономически интерпретированы следующим образом. Исходная задача. Сколько и. какой продукции xj (j =1,2, ., ) необходимо произвести, чтобы при заданных стоимостях Cj (j =1,2, ., ) единицы продукции и размерах имеющихся ресурсов bi (i =1,2, .,

) максимизировать выпуск продукции в стоимостном выражении. Д в о й с т в е н н а я з а д а ч а. Какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости единицы продукции Ci минимизировать общую стоимость затрат? Переменные уi называются оценками или учетными, неявными ценами. Многие задачи линейного программирования первоначально ставятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования. 2. Несимметричные двойственные задачи. Теорема двойственности. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной — в виде неравенств, причем в последней переменные могут быть и отрицательными. Для простоты доказательств постановку задачи условимся записывать в матричной форме. Исходная задача. Найти матрицу-столбец X = (x1, x2, , x ), которая удовлетворяет ограничениям (1.1) AX = A0, Х ( 0 и минимизирует линейную функцию Z = СХ. Двойственная задача. Найти матрицу-строку Y = (y1, y2, , ym), которая удовлетворяет ограничениям (1.2) YA ( С и максимизирует линейную функцию f = YA0 В обеих задачах C = (c1, c2, , c ) - матрица-строка, A0 = (b1, b2, , bm) — матрица-столбец, А = (aij) — матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двойственных задач устанавливает следующая теорема. Теорема (теорема двойственности). Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение mi Z = max f. Если линейная функция одной из задач не ограничена, то другая не имеет решения. Д о к а з а т е л ь с т в о. Предположим, что исходная задача обладает оптимальным планом, который получен симплексным методом. Не нарушая общности, можно считать, что окончательный базис состоит из т первых векторов A1, A2, ., Am. Тогда последняя симплексная таблица имеет вид табл. 1.1. Т а б л и ц а 1.1 i Базис С A0 C1 C2 Cm Cm 1 c базис а A1 A2 Am Am 1 A 1 A1 C1 x1 1 0 . 0 x1, m 1 x1 2 A2 C2 0 1 . 0 x2, m 1 x2 . . . x2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . m Am Cm . 0 0 . 1 xm, m 1 xm . . xm . m 1 Zi - Cj Z0 Z1 – C1 Z2 – C2 . Zm – Cm Zm 1 – Z – . Cm 1 C Пусть D — матрица, составленная из компонент векторов окончательного базиса A1, A2, ., Am; тогда табл. 1.1 состоит из коэффициентов разложения векторов A1, A2, ., A исходной системы по векторам базиса, т. е. каждому вектору Aj в этой таблице соответствует такой вектор Xj что (1.3) Aj = DXj (j= 1,2, ,., ). Для оптимального плана получаем (1.4) A0 = DX , где X = (x 1, x 2, , x m). Обозначим через матрицу, составленную из коэффициентов разложения векторов Аj (j = 1, 2, ., ), записанных в табл. 1.1. Тогда, учитывая соотношения (1.3) и (1.4), получаем: (1.5) A = D, (1.6) A0=DX ; D-1A0 = X , (1.7) mi Z= C X , (1.8) —C ( 0, где С = (C 1, C 2, , C m), С = (C1, C2, , Cm, Cm 1, , C ), a = (C X1 – C1; С Х2 - С2, ., C X – C ) = (Z1 – С1; Z2 - C2; ., Z — C ) — вектор, компоненты которого неположительны, так как они совпадают с Zj — Cj ( 0, соответствующими оптимальному плану.

Оптимальный план исходной задачи имеет вид X = D-1 А0, поэтому оптимальный план двойственной задачи ищем в виде (1.9) Y = C D-1. Покажем, что Y действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA — С ( 0, в левую часть которого подставим Y . Тогда на основании (1.9), (1.5) и (1.8) получим Y А – С = С D-1А – С = С - С ( 0, откуда находим Y A ( С. Так как Y удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двойственной задачи f (Y ) = Y A0. Учитывая соотношения (1.9), (1.6) и (1.7), имеем (1.10) f (Y ) = Y A0 = C D-1 A0 = C X = mi Z(X). Таким образом, значение линейной функции двойственной задачи от Y численно равно минимальному значению линейной функции исходной задачи. Докажем теперь, что Y является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA0=f (Y), YAX ( СХ = Z (X), отсюда следует, что для любых планов Х и Y выполняется неравенство (1.11) f (Y) ( Z (X). Этим же соотношением связаны и экстремальные значения max f (Y) ( mi Z (Х). Из последнего неравенства заключаем, что максимальное значение линейной функции достигается только в случае, если max f (Y) = mi Z (X), но это значение f (Y) достигает при плане Y , следовательно, план Y — оптимальный план двойственной задачи. Аналогично можно доказать, что если двойственная задача имеет решение, то исходная также обладает решением и имеет место соотношение max f (Y) = mi Z (X). Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из (1.11) следует, что f (Y) ( -( . Это выражение лишено смысла, следовательно, двойственная задача не имеет решений. Аналогично предположим, что линейная функция двойственной задачи не ограничена сверху. Тогда из (1.11) получаем, что Z (X) ( (. Это выражение также лишено смысла, поэтому исходная задача не имеет решений. Доказанная теорема позволяет при решении одной из двойственных задач находить оптимальный план другой. Исходная задача. Найти минимальное значение линейной функции Z = x2 – x4 – 3x5 при ограничениях x1 2x2 - x4 x5 = 1, - 4x2 x3 2x4 – x5 = 2, xij ( 0 (j = 1, 2, , 6) 3x2 x5 x6 = 5, Здесь матрица-строка С = (0;. 1; 0; —1; — 3, 0), матрица-столбец 1 1 2 0 -1 1 0 A0 = 2 A = 0 -4 1 2 -1 0 3 0 3 0 0 1 1 1 0 0 2 -4 3 A’’ = 0 1 0 -1 2 0 1 -1 0 0 0 1 Двойственная задача. Найти максимальное значение линейной функции f = y1 2y2 5y3 при ограничениях y1 ( 0, 2y1 – 4y2 3y3 ( 1, y2 ( 0, -y1 2y2 ( -1, y1 – y2 y3 ( -3, y3 ( 0. Решение исходной задачи находим симплексным методом (табл. 1.2). i Базис С A0 0 1 0 -1 -3 0 базиса A1 A2 A3 A4 A5 A6 1 A1 0 1 1 2 0 -1 1 0 2 A3 0 2 0 -4 1 2 -1 0 3 A6 0 5 0 3 0 0 1 1 m 1 Zi - Cj 0 0 -1 0 1 3 0 1 A5 -3 1 1 2 0 -1 1 0 2 A3 0 3 1 -2 1 1 0 0 3 A6 0 4 -1 1 0 1 0 1 m 1 Zi - Cj -3 -3 -7 0 4 0 0 1 A5 -3 4 2 0 1 0 1 0 2 A4 -1 3 1 -2 1 1 0 0 3 A6 0 1 -2 3 -1 0 0 1 m 1 Zi - Cj -15 -7 1 -4 0 0 0 1 A5 -3 4 3 0 1 0 1 0 2 A4 -1 11/3 -1/3 0 1/3 1 0 2/3 3 A2 1 1/3 -2/3 1 -1/3 0 0 1/3 m 1 Zi - Cj -46/3 -19/3 0 -11/3 0 0 -1/3 Оптимальный план исходной задачи X = (0; 1/3; 0; 11/3; 4; 0), при котором Zmi = - 46/3, получен в четвертой итерации табл.

Рассуждают аналитически, если из данной для доказательства теоремы выводят эквивалентные ей очередные следствия, приводя, в конце концов, к такому следствию, которое является уже признанной теоремой, и достигая таким способом обоснования теоремы, которая дана для доказательства. Этому способу рассуждения противостоит синтетический (прогрессивный) метод, когда, имея для доказательства данную теорему, исходят из какой-то другой, уже доказанной теоремы, и выводят из нее данную теорему как следствие, доказывая ее таким путем. Первый метод считается способом инвенции исследования, второй — способом интерпретации достигнутых результатов. Вот что по этому поводу высказал известный специалист в области управления Гамильтон Черч: «Целесообразность и эффективность направляемой нами деятельности будут прямо пропорциональны тонкости и точности нашего анализа, правильности и безошибочности нашего синтеза. Если наши синтетические способности слабее аналитических, то у нас получаются только академические и теоретические „системы“

1. Модифицированный симплекс-метод с мультипликативным представлением матриц

2. Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

3. Построение экономической модели с использованием симплекс-метода

4. Построение экономической модели c использованием симплекс-метода

5. Построение экономической модели c использованием симплекс-метода

6. Табличный симплекс-метод
7. Понятие, предмет, методы, принципы, нормы, источники и система налогового права
8. Решение задач линейного программирования симплекс методом

9. Симплекс метод в форме презентации

10. Графический метод и симплекс-метод решения задач линейного программирования

11. Решение задачи линейного программирования симплекс-методом

12. Состав и функционирование ИС построенной по принципу "клиент-сервер" для численного обоснования решений

13. Способ доказательства теоремы Ферма в общем виде с помощью методов элементарной математики

14. Доказательство Великой теоремы Ферма с помощью метода бесконечных (неопределенных) спусков

15. Теорема Пифагора и способы ее доказательства

16. Двойственность Познания по Учению Св. Григория Паламы (Double Knowledge According to Gregory Palamas)

Цветные карандаши Color Peps, трехгранные, 24 цвета.
Цветные карандаши Color Peps от Maped удовлетворят все потребности детей. Треугольная форма для удобного использования. Мягкий и прочный
433 руб
Раздел: 13-24 цвета
Светильник садовый плавающий на солнечных батареях "Лилия розовая".
Декоративный солнечный садовый светильник в виде лилии, водонепроницаемый. Применяется для декорации пруда. Светодиод меняет цвет.
413 руб
Раздел: Необычные светильники
Набор детской складной мебели "Маша и Медведь. Азбука 3".
Комплект складной, подходит для кормления, игр и обучения. Поверхность столешницы ламинированная с нанесением ярких познавательных
1971 руб
Раздел: Наборы детской мебели

17. Нормирование труда. Принципы, методы, формы

18. Двойственный характер поведения участников и свидетелей войны 1812 г.

19. Центральная предельная теорема и ее доказательство через ряды Тейлора

20. Элементарное доказательство Великой теоремы Ферма

21. Эвристические методы решения творческих задач

22. История доказательства Великой теоремы Ферма
23. Двойственная природа света, ее проявления. Шкала электромагнитных волн
24. Принципы и методы составления ландшафтной карты территории Каменной степи

25. Теорема Ферма: история и доказательства

26. Перестрахование: назначение, принципы и методы

27. Доказательства и методы изучения эволюции органического мира

28. Предмет, метод и принципы семейного права

29. Предмет, метод, система, принципы и источники трудового права

30. Древнегреческая женщина: идеальная двойственность

31. Доказательство Великой теоремы Ферма за одну операцию

32. Доказательство теоремы Ферма для n=4

Сумка для прогулочной коляски Altabebe, арт. AL1004.
Функциональная и простая. Нет необходимости долго искать мелкие предметы в вашей сумке - теперь вы можете легко найти их, воспользовавшись
1040 руб
Раздел: Сумки и органайзеры
Лоток для кухни раздвижной, 30(50,5)х42,5x6,5 см.
Для хранения столовых приборов. Беречь от огня (t -40+100 C). Срок годности не ограничен. Размер: 30(50,5)х42,5x6,5 см
561 руб
Раздел: Лотки для столовых приборов
Папка-сумка "Тролли", А4.
Папка текстильная формованная из вспененного полимера. Формат: А4. Лицевая сторона с выдавленными элементами 3D.
481 руб
Раздел: Папки-портфели, папки с наполнением

33. Записать задачу двойственную к данной, решить одну из пары задач и отыскать оптимальное решение второй

34. Великая теорема Ферма – два коротких доказательства

35. Доказательство великой теоремы Ферма

36. Доказательство великой теоремы Ферма

37. Общие принципы, методы и средства интенсивной терапии

38. Методы и принципы регулирования социально-трудовых отношений на предприятиях в условиях кризиса
39. Основные принципы и методы управленческой психологии
40. Принципы и методы планирования

41. Рационализация методов и приемов труда. Принципы экономии движений.

42. Эвристические методы, их общая характеристика

43. Основні принципи та нетрадиційні методи викладання українського народознавства в школі

44. Дидиктические принципы и методы преподавания ИЗО в начальных классах

45. Основные принципы и методы применения технических регламентов

46. Эвристические методы решения творческих задач

47. Принципы и методы социальной работы, цели, задачи

48. Методы и принципы таможенного права

Тетрадь общая с магнитной закладкой "FLUOR. Желтый", В5, 120 листов, клетка.
Формат - В5. Закладка - ляссе. Внутренний блок - офсет, клетка. Обложка - мелованный картон. Скрепление - книжный переплет. Отделка -
418 руб
Раздел: Прочие
Настольная игра "На память".
Следите за тем, в каком порядке загораются кнопки, а затем правильно повторите последовательность загоравшихся цветов! Отличная игра,
310 руб
Раздел: Прочие
Коляска для кукол "Лили".
4-х колесная коляска. Материал: высококачественная пластмасса. Возраст: с 3 лет. Размер: 27,5х36,5х49 см. Вес коляски: 600
380 руб
Раздел: Коляски прогулочные, трости

49. Принцип полярографического метода

50. Принципи і методи планування у виробничій сфері

51. Двойственность в линейном программировании

52. Метод конечных элементов

53. Принцип работы и назначение телескопа

54. Изучение миксомицетов среднего Урала, выращенных методом влажных камер
55. Методы исследования в цитологии
56. МЕТОДЫ ИЗУЧЕНИЯ ЭВОЛЮЦИИ ЧЕЛОВЕКА

57. Методологическое значение сравнительного метода в зоологических исследованиях

58. Метод радиоавтографии в биологии

59. Основные принципы создания группировок войск для сражения, принятия решения командованием и организации управления

60. Зажигательные смеси, состав, средства применения и доставки, вызываемые повреждения, методы лечения и защиты

61. Методы и модели демографических процессов

62. Гидрохимический, атмохический и биогеохимический методы поисков

63. Добыча золота методами геотехнологии

64. Принцип построения налога на добавленную стоимость

Брелок "FIFA 2018. Забивака. Фристайл!".
Брелок с символикой чемпионата мира FIFA 2018. Материал: ПВХ.
348 руб
Раздел: Брелоки, магниты, сувениры
Набор цветных карандашей для правшей STABILO EASYcolors, 12 штук c точилкой.
В наборе 12 цветных карандашей + точилка. Первые трехгранные цветные карандаши, специально разработанные для левшей и для правшей. •
1771 руб
Раздел: 7-12 цветов
Сухой бассейн "Крокодил" + 50 шаров.
В комплекте: надувная площадка, 50 пластиковых шариков разного цвета диаметром 6 см. Материал: ПВХ пленка, пластмасса. Размер игрушки:
1813 руб
Раздел: Батуты, надувные центры

65. Основні методи боротьби з інфляцією

66. Сущность, методы и формы государственного регулирования внешнеэкономической деятельности Российской Федерации

67. Участие адвоката в исследовании доказательств

68. Понятие и принципы административной ответственности

69. Методы осуществления государственной власти

70. Письменные доказательства в арбитражном процессе
71. Предмет и метод гражданского права
72. Вещественные доказательства в гражданском процессе

73. Принципы гражданского процессуального права

74. Принципы гражданского процессуального права

75. Предмет, метод и система гражданского процессуального права /Украина/

76. Формы и методы государственного регулирования экономики в Казахстане

77. Понятие, содержание и принципы исполнительной власти

78. Математические методы и модели в конституционно-правовом исследовании

79. Формы и методы выхода предприятий на внешний рынок

80. Принципы технического регулирования, порядок разработки, принятия технических регламентов

Форма разъемная Regent "Easy" круглая, 18x7 см.
Форма для выпечки разъемная из углеродистой стали с антипригарным покрытием. Удобная застежка. Поверхность устойчива к царапинам. Диаметр:
310 руб
Раздел: Формы и формочки для выпечки
Стиральный порошок Lion "Blue Diamond", 900 грамм.
Высокоэкономичный стиральный порошок предназначен для ручной и автоматической стирки белья из хлопка, синтетики и смешанных
344 руб
Раздел: Стиральные порошки
Медицинская карта истории развития ребенка, красная, А5, по форме 112/У.
История развития ребенка — основной медицинский документ, который ведется на каждого ребенка от рождения и до 14 лет включительно. В этот
498 руб
Раздел: Бланки, книги учета

81. Право: понятие, признаки, виды, функции, принципы

82. Принцип разделения властей

83. Происхождение права, теории происхождения права, понятие признаки, виды, функции, принципы

84. Принцип разделения властей

85. Методы комплексной оценки хозяйственно-финансовой деятельности

86. Цикл-метод обучения. (Методика преподавания эстонского языка)
87. Специфика преподавания иностранного языка и метод проектов
88. Метод действенного анализа в режиссуре театра, кино и телевидения

89. Естественная и гуманитарная культуры. Научный метод

90. Русская здрава (методы оздоровления на Руси)

91. Принцип аналогии в морфологии

92. Методы изучения музыкальных произведений крупной формы в старших классах общеобразовательной школы

93. Цивилизационные методы в изучении истории

94. Методы компьютерной обработки статистических данных

95. Решение транспортной задачи методом потенциалов

96. Решение дифференциальных уравнений 1 порядка методом Эйлера

Пустышки силиконовые Avent "Ночная", розовый (6-18 месяцев), 2 штуки.
Симметричные мягкие ортодонтические соски пустышек Avent от Philips учитывают естественное строение и развитие неба, зубов и десен
660 руб
Раздел: 6-18 месяцев
Набор ковриков "Kamalak Tekstil" для ванной, 50х50 см и 50x80 см (синий).
Ковры-паласы выполнены из полипропилена. Ковры обладают хорошими показателями теплостойкости и шумоизоляции. Являются гипоаллергенными. За
607 руб
Раздел: Коврики
Форма для выпечки разъемная "Appetite", 20х7 см.
Форма для выпечки с антипригарным покрытием, разъемная. Размер: 20х7 см.
371 руб
Раздел: Формы и формочки для выпечки

97. Принципы работы системы управления параллельными процессами в локальных сетях компьютеров

98. Разработка методов определения эффективности торговых интернет систем

99. Телекоммуникационные компьютерные сети: эволюция и основные принципы построения


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.