Студопедия  
Главная страница | Контакты | Случайная страница

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

Общий вид задачи линейного программирования.

Читайте также:
  1. Cельскохозяйственное картографирование, его особенности и задачи.
  2. I группа: задачи на решение проблем в обучении
  3. I Цели и задачи изучения дисциплины
  4. I. Общий осмотр больного
  5. I. Общий осмотр больного.
  6. I. Общий осмотр больного.
  7. I. Семинар. Тема 1. Предмет, система, задачи судебной медицины. Правовые и организационные основы судебно-медицинской экспертизы, Понятие, объекты, виды, экспертизы
  8. I. Цель и задачи дисциплины
  9. II. Типовые задачи.
  10. II. Цели и задачи выпускной квалификационной работы

Линейное программирование – это математическая дисциплина, которая изучает методы нахождения min или max значения линейной функции нескольких переменных при условии, что все эти переменные удовлетворяют конечному числу линейных уравнений и неравенств.

Задача линейного программирования:

Функция цели: Z = c1x1+c2x2+…+cnxn => min (max)

@ - любое равенство или неравенство.

a11x1+…+a1nxn@b1

. . . . . . . . . . . . . . . . . . . . . . .

am1x1+…+amnxn@bn, x1>=0, . . ., xn>=0.

Каноническая форма представления задач линейного программирования. (2)

Линейное программирование – это математическая дисциплина, которая изучает методы нахождения min или max значения линейной функции нескольких переменных при условии, что все эти переменные удовлетворяют конечному числу линейных уравнений и неравенств.

Z = c1x1+c2x2+…+cnxn => max

a11x1+…+a1nxn = b1

. . . . . . . . . . . . . . . . . . . . . . .

am1x1+…+amnxn = bm, x1>=0, . . ., xn>=0.

Только равенства.

 

Ограничения в задачах линейного программирования, перевод задач линейного программирования в каноническую форму. (2)

Линейное программирование – это математическая дисциплина, которая изучает методы нахождения min или max значения линейной функции нескольких переменных при условии, что все эти переменные удовлетворяют конечному числу линейных уравнений и неравенств.

Ограничения в виде неравенств можно преобразовать в равенство. Для этого вводится xn+1:

ai1x1+ai2x2+. . .+ainxn+bi>=0, отсюда:

ai1x1+ai2x2+. . .+ainxn+bi= xn+1, xn+1>=0.

Для того, чтобы наложить условие неотрицательности необходимо вместо одной переменной, например xi, заменить на две переменные: xi>=0 и xi­’’>=0, отсюда xi= xi- xi’’.

Возможно и обратное! Любую задачу линейного программирования можно сформулировать таким образом, чтобы все ограничения были в виде неравенств.

Понятия допустимого, оптимального решения, линейной формы задач ЛП. (2)

Любое неотрицательное решение в данной задаче (в задаче ЛП) называется допустимым решением, а вот допустимое решение, которое дает min или max целевой функции называется оптимальным решением. Оптимальное решение не обязательно является единственным и не обязательно оно вообще существует. Саму целевую функцию иногда называют линейной формой. Суть задач ЛП: из множества допустимых решений выбрать то, которое обращает линейную форму в min или max.

Геометрическая интерпретация задач линейного программирования. (2)

Любую задачу линейного программирования можно представить геометрически. Для этого все ограничения лучше записать в виде неравенств:

ai1x1+ai2x2+…+ainxn>=bi

(полупространство, все переменные лежат по одну сторону от плоскости)

 

 

В итоге мы получаем некое пересечение множеств, которое образует в пространстве выпуклый многогранник. Значение целевой функции z в произвольной точке х можно рассматривать, как уклонение точки х от плоскости z=0.

Получаем геометрический смысл задач ЛП – это отыскание в полученном многограннике Ω тех точек, которые наименее или наиболее удалены от плоскости z=0.

 

Понятие базисных и свободных переменных. (2)

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

Клетки таблицы ненулевые называются базисными клетками и соответствующие переменные – базисные переменные. Остальные клетки называются свободными, которые составляют опорное решение (для транспортной задачи).

 


Дата добавления: 2015-02-16; просмотров: 19 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2020 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав