bannerka.ua

Метод искусственного базиса

Метод искусственного базиса

1. На предыдущей лекции были рассмотрены задачу, записанную в форме основной задачи ЛП, для которой можно было указать ее опорный план, потому что среди векторов Pj, координатами которых являются коэффициенты при неизвестных в системе уравнений данной задачи, было m единичных. Но для многих задач ЛП, записанных в форме основной задачи и имеющих опорные планы, среди векторов Pj не всегда M единичных.

Рассмотрим такую задачу.

Пусть требуется найти максимальное значение функции

F=C1X1+C2X2+… +Cnxn (1)

При условиях

Метод искусственного базиса (2)

Где Метод искусственного базисаИ среди векторов

Метод искусственного базиса Метод искусственного базиса . . . Метод искусственного базиса

Есть m единичных векторов.

Определения. Задача в которой нужно найти максимальное значение функции

F=C1X1+C2X2+… +Cnxn - МхN+1 - … -Mxn+M (3)

При условиях

Метод искусственного базиса (4)

Где М — Некоторое достаточно большое положительное число, конкретное значение которого как правило не задается, называется расширенной задачей по отношению к задаче (1) — (2).

Дополнительная задача имеет опорный план Х = (0, 0; …; 0; B1; B2; …; Bm),

Метод искусственного базиса

N нулей

Что определяется системой единичных векторов Pn+1, Pn+2, …, Pn+M, образующих базис

m-го векторного пространства, получивший название Искусственного. Векторы Pn+1, Pn+2, …, Pn+M и переменные Метод искусственного базиса называют Искусственными. Если задача (1) — (2) имеет несколько единичных векторов, то их нужно включить в искусственный базис. Так как расширенная задача имеет опорный план, то ее решение можно найти симплексным методом. Для этого:

Составляют расширенную задачу (3) — (4). Находят опорный план расширенной задачи. Составляют первую симплексной таблицы, содержащей на одну строку больше, чем обычная таблица. При этом в (M+2)Строка записывают коэффициенты при М, а в (M+1)-и — слагаемые, не содержащие M.

При переходе от одного опорного плана к другому в базис вводят переменную, соответствует наибольшему по модулю отрицательном числу (M+2)- й строки. Искусственную переменную, выводимого из базиса в результате некоторой итерации, в дальнейшем не имеет смысла вводить в один из следующих базисов и поэтому нецелесообразно вычислять столбик этой переменной.

Итерационный процесс по (M+2)- й строчке ведут до тех пор, пока:

I. все искусственные переменные не будут исключены из базиса. В этом случае базис соответствует некоторому опорному плану задачи (1) — (2) и определение ее оптимального плана продолжают по (M+1)- й строчке.

II. не все искусственные переменные выведены из базиса, но (M+2) -И строка не содержит больше отрицательных элементов в столбцах переменных Х1, х2, … , ХN+M. Если элемент (M+2) -Й строки колонки Р0 отрицательный, то задача (1) — (2) не имеет решения, если же он равен нулю то найденный опорный план будет содержать хотя бы одну искусственную переменную.

4. Используя найден опорный план задачи (1) — (2), или находят симплексным методом оптимальный план этой задачи, или устанавливают ее нерозришимисть.

2. Терминологический словарь

Задача в которой нужно найти максимальное значение функции

F=C1X1+C2X2+… +Cnxn - МхN+1 - … -Mxn+M

При условиях

Метод искусственного базиса

Где М — Некоторое достаточно большое положительное число, конкретное значение которого как правило не задается, называется Расширенной задачей по отношению к задаче (1) — (2).

Дополнительная задача имеет опорный план Х = (0, 0; …; 0; B1; B2; …; Bm),

Метод искусственного базиса

N нулей

Что определяется системой единичных векторов Pn+1, Pn+2, …, Pn+M, образующие Базис

m-го векторного пространства, получивший название Искусственного. Векторы Pn+1, Pn+2, …, Pn+M и переменные Метод искусственного базиса называют Искусственными.

3. Рекомендуемая литература

1. Богаенко И. М., Григорков BC, Бойчук М. В., Рюмашин М.0. Математическое программирование: Учеб. пособие. — М.: Логос, 1996.

2. Бугир М. К. Тетрадь для практических занятий по математическому программированию. — Тернополь: Учебники и пособия, 1999.

3. Бугир М. К. Математика для экономистов. Линейная алгебра, линейные модели: Учеб. пособие. — К.: ВЦ «Академия», 1998.

4. Гвоздинський А. М. Оптимизационные задачи в организационном управлении: Учеб. посиб.-Харьков: ХГТУРЭ, 1997.

5. Гетманцев В. Д. Линейная алгебра и линейное программирование:

Уч. пособие. — М.: Просвещение, 2001.

6. Григорков BC, Бойчук М. В. Практикум по математическому программированию: Учеб. пособие. — Черновцы: Прут, 1995.

7. Деордица Ю. С., Савченко В. Т. Компьютерные технологии в экономике и менеджменте: Учеб. пособие. — Луганск: ВУГУ, 1999.

8. Зайченко Ю. П. Исследование операций: Учебник. — М.:

ВШОЛ, 2000.

9. Исследование операций в экономике: Учеб. пособие / Под ред. Н. Ш. Кремера. — М.: ЮНИТИ, 1999.

10. Кигель В. Р. Элементы линейного, целочисленного линейного, нелинейного программирования: Учеб. пособие. — М.: ИСДО, 1995.

11. Мазараки А. А., Толбатов Ю. А. Математическое программирование в Ехсе1: Учеб. пособие. — К.: Четвертая волна, 1998.

12.Романюк Т. П., Терещенко Т. А., Присенко Г. В., Городкова И. М. Математическое программирование: Учеб. пособие. — М.: ИЗМН, 1996.

13.Цегелик Г. Г. Линейное программирование: Учеб. пособие. — М.: Мир, 1995.

14.Экономико-математические методы и прикладные модели: Учеб. пособие / Под ред. В. В. Федосеев. — М.: ЮНИТИ, 1999.

15.Крушевський А. В. Справочник по экономико-математическим моделям и методам. — К.: Техника, 1982, — 208 с.

Iб. Вивальнюк Л. М. Элементы линейного программирования. — М.: Вищашк., 1975, -191 с.

Tagged with: , ,
Posted in Математические модели в расчетах на эвм
No Comments » for Метод искусственного базиса
2 Pings/Trackbacks for "Метод искусственного базиса"
  1. […] метод искусственного базиса […]

Добавить комментарий

Ваш e-mail не будет опубликован.

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Перечень предметов
  1. Бухучет в ресторанном хозяйстве
  2. Введение в специальность 4к.2с
  3. Высшая математика 3к.1с
  4. Делопроизводство
  5. Информационные технологии в области
  6. Информационные технологии в системах качества стандартизаціісертифікаціі
  7. История украинской культуры
  8. Математические модели в расчетах на эвм
  9. Методы контроля пищевых производств
  10. Микробиология молока и молочных продуктов 3к.1с
  11. Микропроцессорные системы управления технологическими процессами
  12. Научно-практические основы технологии молока и молочных продуктов
  13. Научно-практические основы технологии мяса и мясных продуктов
  14. Общая технология пищевых производств 4к.2с
  15. Общие технологии пищевых производств
  16. Организация обслуживания в предприятиях ресторанного хозяйства
  17. Основы научных исследований и техничнои творчества
  18. Основы охраны труда
  19. Основы пидприемницькои деятельности и агробизнеса
  20. Основы физиологии и гигиены питания 3к.1с
  21. Пищевые и диетические добавки
  22. Политология
  23. Получения доброкачественного молока 3к.1с
  24. Прикладная механика
  25. Прикладная механика 4к.2с
  26. Теоретические основы технологии пищевых производств
  27. Технологический семинар
  28. Технологическое оборудование для молочной промышленности
  29. Технологическое оборудование для мьяснои промышленности
  30. Технология продукции предприятий ресторанного хозяйства
  31. Технология хранения консервирования и переработки молока
  32. Технология хранения, консервирования и переработки мяса
  33. Технохимическому контроль
  34. Управление качеством продукции ресторанного хозяйства
  35. Физика
  36. Физическое воспитание 3к.1с
Возможно Вы искали: