• Document: Тема 3. Симплекс-метод решения задачи линейного программирования
  • Size: 225.16 KB
  • Uploaded: 2019-06-13 10:17:06
  • Status: Successfully converted


Some snippets from your converted document:

Тема 3. Симплекс-метод решения задачи линейного программирования Цель: познакомить читателя с симплекс-методом решения задачи линейного программирования и основными понятиями и теоремами тео- рии двойственности в линейном программировании. Задачи:  научиться формулировать стандартную и каноническую задачи ли- нейного программирования, познакомиться с эквивалентными пре- образованиями задачи;  ввести понятие базисного решения для канонической задачи ли- нейного программирования (задача ЛП), сформулировать алгоритм симплекс-метода решения задачи ЛП;  сформулировать теоремы двойственности и равновесия в линей- ном программировании. Дать экономическую интерпретацию тео- рии двойственности. Оглавление § 3.1. Специальные виды задач линейного программирования. Стандарт- ная и каноническая задачи. Матричная форма записи. § 3.2. Эквивалентные формулировки. Эквивалентные преобразования § 3.3. Базисное решение системы линейных уравнений. § 3.4. Алгоритм симплекс-метода решения задачи ЛП. Геометрическая интерпретация. § 3.5. Прямая и двойственная задача линейного программирования. Свойства. § 3.6. Теоремы двойственности и равновесия в линейном программиро- вании. § 3.1. Специальные виды задач линейного программирования. Стандартная и каноническая задачи. Матричная форма записи Напомним, что математически задача ЛП – это задача нахождения наибольшего (наименьшего) значения линейной функции многих пере- менных при линейных ограничениях типа равенства или нестрогого не- равенства, когда на переменные задачи есть (нет) ограничений на знак. Формально это означает, что задачу максимизации можно записать так: 1 max z  max(c1x1    cn xn ), ai 1x1    ain xn  bi , i  1, m1, ai 1x1    ain xn  bi , i  m1  1, m, x j  0, j  1, n1, x j  0, j  n1  1, n. Аналогично можно написать общую постановку для задачи миними- зации min z  min(c1x1    cn x n ), ai 1x1    ain xn  bi , i  1, m1, ai 1x1    ain xn  bi , i  m1  1, m, x j  0, j  1, n1, x j  0, j  n1  1, n. Однако симплекс-метод решения задачи предполагает, что задача ЛП записана в одном из специальных видов. Имеется 4 специальных ви- да задачи ЛП (два стандартных и два канонических вида). Стандартная форма задачи ЛП максимизации – это задача нахож- дения максимума целевой функции при ограничениях типа нестрогого неравенства (меньше или равно) и при наличии ограничений на знак для всех переменных (условия неотрицательности): max z  max(c1x1    cn xn ), ai 1x1    ain xn  bi , i  1, m, x j  0, j  1, n. В матричном и векторном виде эта задача может быть записана так: max z  max CX max z  max CX , AX  B или Ai X  bi , i  1, m, , X 0

Recently converted files (publicly available):