АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ДОКАЗАТЕЛЬСТВО. Рассмотрим задачу в канонической форме ( задача сводится к канонической)

Читайте также:
  1. Абсолютное доказательство
  2. Глава 4. Социальное доказательство.
  3. Доказательство
  4. Доказательство
  5. Доказательство
  6. Доказательство
  7. Доказательство
  8. Доказательство
  9. Доказательство
  10. ДОКАЗАТЕЛЬСТВО
  11. ДОКАЗАТЕЛЬСТВО

Рассмотрим задачу в канонической форме ( задача сводится к канонической)


По условию, задача разрешима, те

Выберем любое оптимальное решение

1) Если оно является опорным ч.т.д

2) не является опорным

Будем считать, что первые k координат положительные

Но т.к. - не является опорным решением, то

Следовательно cсуществуют отличные от нуля

Всегда будем считать, что есть такие, что не равны нулю.

Но с другой стороны существует нетривиальное решение системы уравнений , а т.к. оно однородное, то существует решение с точностью до знака

Допишем к системе (2) уравнение

Получим:

Решение системы:

Теперь определим так, чтобы

Получим общее решение данной системы:

– всегда конечное положительное число (т.к. есть всегда)

величина отрицательная (может быть )

Учитывая однородность (2), можно утверждать, что (*)

Чтобы убедится в конечности , построим семейство дополнительных решений задачи

Заметим, что оно имеет меньше чем положительных компонент.

Докажем, что все эти решения являются оптимальными

Для этого докажем, что

Рассмотрим целевую функцию:

Из неравенства получаем, что

Т.к. на принимает как положительные, так и отрицательные значения, то

Тогда

Следовательно – оптимальное решение задачи.

Итерируя описанный процесс преобразования , через конечное число итераций получим оптимальное опорное решение.

¤

ВЫВОД

Чтобы решить задачу линейного программирования, достаточно перебрать опорные решения системы линейных уравнений.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)