2.4. Содержание отчета.

1. Описание симплексного метода и алгоритма его программной реализации.

2. Текст программы.

3. Таблицы результатов, включая промежуточные симплексные таблицы.

4. Графическая интерпретация результатов.

5. Сравнение с решением, полученным при помощи таблиц EXCEL.

2.5. Вопросы для самопроверки.

1. Чем отличаются условия оптимальности для основных задач линейного программирования на максимум и на минимум?

2. Как может быть сформулировано условие неограниченности целевой функции снизу?

3. Каким образом в рамках симплексного метода устанавливается неразрешимость задачи в силу отсутствия планов (противоречивости ограничений задачи линейного программирования)?

4. Что является признаком неединственности оптимального плана?

5. Как влияет погрешность вычислений на решение основной задачи линейного программирования симплексным методом?

Лабораторная работа № 3 Тема: Решение основной задачи линейного программирования двойственным симплексным методом.

1. Цель работы и задачи работы.

Цель работы - разработка и программная реализация алгоритма нахождения оптимального плана основной задачи линейного программирования на основе обобщенного двойственного симплексного метода. Экспериментальная проверка (на основе вычислительного эксперимента) теоретических положений.

Задачи работы:

• Ознакомление с понятием двойственности в задачах линейного программирования.

• Изучение двойственного симплексного метода решения основной задачи линейного программирования.

3.2. Краткие теоретические сведения.

Двойственные задачи линейного программирования
Задача I	Задача II
F=cj xj  max	F*=bi yi  min
aij xj  bi (i=1,2,…,k)	yi aij  cj (j=1,2,…,s)
aij xj = bi (i= k +1,..., m)	yi aij = cj (j=s+1,…,n)
xj  0 (j=1,2,…,s)	yi  0 (i=1,2,…,k)

Определение 3.1. Задача линейного программирования II называется двойственной по отношению к задаче линейного программирования I (исходной).

Свойства двойственных задач.

Утверждение 3.1.

Задача III, двойственная по отношению к задаче II, совпадает с задачей I, т.е. нет смысла в определении, какая из двух задач является исходной, какая – двойственной. Можно говорить о паре двойственных задач.

Утверждение 3.2.

Если X – план задачи I., а Y – план задачи II, то F(X)  F*(Y).

Утверждение 3.3.

Если задача I (задача II) не имеет решения в силу неограниченности сверху (снизу) целевой функции, то задача II (задача I) не имеет решения в силу отсутствия планов.

Утверждение 3.4.

Если X* – оптимальный план задачи I, а Y* – оптимальный план задачи II, то F(X*) =F*(Y*).

Определение 3.2. Базисное решение основной задачи линейного программирования на максимум X называется псевдопланом, если _j0, т.е. все оценки неотрицательны.

Условия оптимальности и разрешимости.

Условие 3.1.

Если все компоненты псевдоплана X=(x₁, x₂, x₃ ,…, x_m,,0,…,0) неотрицательны, т.е. x_j  0 , (j=1,..,n), то X – оптимальный план.

Условие 3.2.

Если X=(x₁, x₂, x₃ ,…, x_m,,0,…,0) – псевдоплан основной задачи линейного программирования и если  k : x_k <0, 1  k n и a_ik  0 i, i=1,...,m,, то основная задача линейного программирования не имеет решений в силу отсутствия планов.

Условие 3.3.

Если X=(x₁, x₂, x₃ ,…, x_m,,0,…,0) – псевдоплан основной задачи линейного программирования и если  k, i (1  k n, 1  i  m) : x_k <0, (1  k n, 1  i  m) a_ik  0 i, i=1,...,m, то можно перейти к другому псевдоплану, при котором значение целевой функции не увеличится.