Теперь  составляется новая таблица. В столбце "Базис" вместо старой переменной - x_q пишем новую - x_s. Опять на пересечении основных переменных ставим 1, а остальные клетки в столбцах основных переменных заполняем нулями (включая нижнюю строку). Далее, новую строку с номером q получаем путём деления старой строки на разрешающий элемент (a_qs), при этом считаем только пустые клетки (те которые в столбцах неосновных переменных).

    Остальные клетки считаем по следующим формулам:

    новая a_ij ровна старой a_ij-a_is*a_qj/a_qs

    новая b_i ровна старой b_i-a_is*b_q/a_qs

    новая c_j ровна старой c_j-c_s*a_qj/a_qs

    Клетка  c₀ заполняется как старая c₀-c_s*g_q.

    Затем снова проверяем решение на оптимальность, если оно не оптимально ищем разрешающий  элемент и так далее, пока не найдём оптимума.

    Но  возможны и другие ситуации - особые случаи симплексного метода. Например, задача не имеет решения, если все оценочные отношения g_i равны нулям и бесконечностям. Кроме того, задача так же может зациклиться. Эти случаи тоже следует учитывать. 

Реализация  алгоритма

 
 

    Программа  реализуется с применением модульного  принципа.

    Сначала  программа при выборе открытия файла загружает ссылку на файл.

    После  этого нажимаем кнопку запуска оптимизации.

    Метод Load_From_File() читает содержимое файла  и передает его на обработку.

    Метод Transponate_Matrix() транспонирует матрицу  коэффициентов путем простого переприсваивания элементов с заменой строк на столбцы.

    После  этого вызывается рекурсивный  метод Step_Matrix, который собственно и выполняет всю работу по оптимизации таблицы.

    Рассмотрим  метод подробнее.

    Сначала  определяется минимум по строке функции, т.е. определяется разрешающий столбец.

    После  этого рассчитывается оценочное  отношение, причем используется  очень простой принцип определения  разных знаков при коэффициентах:

    если  отношение меньше нуля, тогда  записать в ячейку оценочного  отношения максимальное значение выбранного типа данных (Например, для типа float таковой является MAXFLOAT). При этом вычислении совмещен поиск минимального значения.

      По полученным координатам (разрешающий столбец и разрешающая строка)

    определяется  разрешающий элемент, на который будет делиться разрешающая строка. 

    Новый  массив заполняется точно также  как на бумаге:

      сначала разрешающая строка делится  на разрешающий элемент;

      потом согласно правилу прямоугольника  рассчитываются значения всех

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

           переменных тоже заполняются  правильно;

      меняем номера элементов в массиве базисов.

    Копируем  в старый массив новую матрицу.

    Записываем  в файл представление матрицы.

    Проверяем, является ли решение конечным

      да,  является, тогда выводим решение  и прерываем рекурсию;

      нет, вызываем снова этот метод.

    После  возврата из основного метода  загружаем в браузер сгенерированный  файл и отображаем его в  программе.

    Помимо  этого в программе реализован  метод создания нового исходного файла путем набора обычного текстового файла в окне редактирования.

    В  программе представлены также  методы вызова информации о  программе, а также загрузки материалов.

    При  написании программы и материалов  были использованы следующие  приложения:

      Среда C++Builder 6, создание собственно  программы.

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

      Изначально код был написан  на языке С++, который является идеальным для  создания программ подобного рода. Среда же имеется очень удобный отладчик, благодаря которому отыскивать ошибки стало намного легче, чем в среде Borland C++ 3.1.

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

     

     Image Editor, Microsoft Paint, создание графики, ярлыка, значков и кнопок.

     Far Menedger, операции с файлами, написание  материалов.

     Internet Explorer, просмотр результатов работы. 
 
 

Выводы  и заключения

 

    Для решения задачи реализации симплекс-метода в случае всех отрицательных свободных членов мы должны прибегнуть к решению двойственной задачи. Это позволяет получить решение по оптимальному решению двойственной задачи, имеющей допустимое начальное решение.

    Задание выполнено, программа работает.

Список  используемых источников информации

 

1. Сайт model.scc.
2. Б.Я Советов, С.А. Яковлев. Моделирование систем. М. Высшая школа,1985
3. Ю.М. Коршунов. Математические основы кибернетики. М.Энергоатомиздат,1987
4. А.А. Горчаков, И.В. Орлова. Компьютерные экономико-математические модели. М.ЮНИТИ,1995
5. А.Н. Колесников. Краткий курс математики для экономистов. М.ИНФА-М,1997
6. В.И. Бережной, Е.В. Бережная Экономико-математические методы и модели в примерах и задачах. Ставрополь,1996
7. Экономико-математические методы и прикладные модели. М.Финстатинформ,1997
8. Б.Я Советов, С.А. Яковлев. Моделирование систем. Практикум. М. Высшая школа,1999
9. С.И. Шелобаев. Математические методы и модели. М. Юнити, 2000
10. В.А. Абчук. Экономико-математические методы. Санкт-Петербург Союз,1999
11. О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемных. Математические методы в экономике. М.ДИС, 1997.

Приложения

     RAR(SFX) архив программы и материалов.