22. Нахождение допустимого базисного плана для задачи линейного программирования.

Пусть система ограничений задачи ЛП задана в каноническом виде:

A1x1+ A2x2+…+ Anxn=B (1)

Целевая функция

μ(х)= С1x1+ С2x2+…+ Сnxn→min (2)

Пусть найдено исходное базисное решение

Х=(b1, b2… bm,0,0…0)

Разложение любого вектора по векторам базиса A1A2…An единственно.

A1x1j+ A2x2j+…+ Anxnj=Aj (3)

Тогда этому разложению Aj в базис соответствует единственное значение целевой функции.

С1x1j+ С2x2j+…+ Сnxn= μ j (4)

μj – значение целевой функции , если в нем вместо неизвестных подставить коэффициент разложения j-го вектора по векторам данного базиса.

Теор. Если верно неравенство μj – Сj>0 для некоторого Aj, то план x(0) не является оптимальным и может быть найден такой план х, что μ(х)< μ(x(0))

Доказательство. Умножим (3) и (4) на ε>0? И результаты вычтем из (1) и (2) соответственно:

A1 (x1 - ε x1j)+ A2 (x2 - ε x2j)+…+ Am (xm - ε xmj)=В- εAj (5)

C1 (x1 - ε x1j)+ C2 (x2 - ε x2j)+…+ Cm (xm - ε xmj)= μ(х) - ε μ j (6)

Перепишем (5) в виде

A1 (x1 - ε x1j)+ A2 (x2 - ε x2j)+…+ Am (xm - ε xmj)+εAj =В

В (6) прибавим ко обоим частям εСj и справа вынесем ε за скобку:

C1 (x1 - ε x1j)+ C2 (x2 - ε x2j)+…+ Cm (xm - ε xmj)+ ε Сj= μ(х)- ε(μj-Сj)

(7) означает, что получим новый опорный план ( новое базисное решение). ε>0, нужно выбрать таким образом, чтобы все коэффициенты A1A2…An были положительные или равные 0.

По условию теоремы μj-Сj>0, ε>0 в силу выбора имеем при подстановки нового базисного решения (7) в условии (8)

μ(х)= μ(x(0))- ε(μj-Сj), значит μ(х)

<< | >>
Источник: Шпаргалка - Математические методы и модели исследования операций. 2016
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме 22. Нахождение допустимого базисного плана для задачи линейного программирования.:

  1. 50. Двойственная задача линейного программирования. Экономическая интерпретация. Связь между базисными и свободными переменными прямой и двойственной задач. С каж
  2. 40. Методы построения допустимого базисного плана для ТЗ в матричной постановке. Открытая и закрытая модели ТЗ, преобразование открытой модели в закрытую.
  3. 18. Критерий оптимальности допустимого базисного плана в симплекс-методе.
  4. Примеры использования симплекс-алгоритма для решения задачи линейного программирования.
  5. 14. Теорема о совпадении угловой точки ОДР с допустимым базисным решением задачи ЛП.
  6. Целочисленные задачи линейного программирования: сфера применения, основные понятия, задача о коммивояжере, задача календарного планирования.
  7. Задача линейного программирования. Приведение задачи к стандартному виду.
  8. 6.1.Задачи линейного программирования.
  9. Семериков А.В.. Решение задач линейного программирования с использованием симплекс метода: Методические указания для выполнения практических работ. – Ухта: УГТУ,2007. – 52 с., 2007
  10. Задача линейного программирования (ЗЛП)
  11. Общая задача линейного программирования.
  12. Общая форма задачи линейного программирования .
  13. №5 Постановка задач линейного программирования.
  14. Двойственно допустимое базисное множество
  15. 7.2.Сведение задач линейного программирования к целочисленным.
  16. Задачи линейного программирования (ЛП).
  17. Задача линейного программирования (ЗЛП)
  18. 9 Транспортная задача линейного программирования
  19. Оценка оптимальности решения задачи линейного программирования симплекс-методом
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -