Решение задач симплексным методом

Автор работы: Пользователь скрыл имя, 12 Ноября 2009 в 18:52, Не определен

Описание работы

1.Краткий обзор алгоритмов решения задач данного типа
2.Содержательная постановка задачи
3.Разработка и описание алгоритма решения задачи
4.Назначение программы
5.Инструкция пользователю
6.Текст исходного модуля

Файлы: 2 файла

simpleks_metod1.xls

— 118.00 Кб (Просмотреть файл, Скачать файл)

курсовик.doc

— 247.00 Кб (Скачать файл)

Dim CurrentPlan As String

Dim i As Integer

Cycle = False

CurrentPlan = “”

For i = 1 To AmRest

CurrentPlan = CurrentPlan & CStr(MiCiXiAi(i, 3))

Next i

If InStr(AllPlans, CurrentPlan) > 0 Then

If DirectCycle = True Then

DirectCycle = False

Else

Cycle = True

End If

AllPlans = “”

Else

AllPlans = AllPlans & ” ”  & CurrentPlan

End If

End Function

 

Заключение

       В данной работе рассматриваются два  способа решения исходной задачи линейного программирования.

       Первый заключается в том, что сначала решается вспомогательная задача (L-задача), позволяющая построить начальный опорный план, затем на основе этого найденного плана решается исходная задача (определяется ее оптимальный план). Второй способ является объединением двух этапов и состоит в решении расширенной задачи (M-задачи), также приводящей к нахождению оптимального плана исходной задачи.

       Вычислительную  основу этих двух способов решения  составляют соответственно первый и второй алгоритмы симплекс-метода. Один из параметров, по которому может быть оценен любой итерационный алгоритм – количество шагов, приводящих к решению задачи или установлению ее неразрешимости. Для данной задачи наиболее эффективным методом оказался первый метод(L-задача + исходная задача), т.к. он привел к решению за 4 шага, а второй метод (M-задача) за 5 шагов. Разница в числе шагов, вероятно, обусловлена неоднозначность выбора разрешающего элемента в исходной таблице L-задачи.

       Сравнение количества вычислений на каждой итерации приводит к следующим оценочным результатам рассматриваемых алгоритмов. Преимущественная часть вычислений на каждом шаге алгоритмов определяется размерностью главной части таблицы (в первом алгоритме) или основной таблицы (во втором алгоритме). В первом случае она имеет размерность (m+1)x(n+1), во втором - (m+1)x(m+1). Даже учитывая, что второй алгоритм требует построения вспомогательной таблицы, он оказывается более компактным.

       Еще одно несомненное достоинство второго  алгоритма заключается в возможности  определения оптимального плана двойственной задачи из (m+1)-й строки основной таблицы, соответствующей последней итерации, без всяких дополнительных вычислений.

 

Список  использованных источников

  1. Вентцель  Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2001.
  2. Аронович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по исследованию операций. – М.: Издательство Московского университета, 1997.
  3. Исследование операций в экономике /Под ред. Кремер. – М.: ЮНИТИ, 1997.
  4. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. – М.: Высшая школа, 1986.
  5. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели управления. – М.: Дело, 2000.
  6. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986.
  7. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. – М.: Мир, 1984.
  8. Липски В. Комбинаторика для программистов. – М.: Мир, 1988.

Информация о работе Решение задач симплексным методом