Реализация симплекс-метода в случае отрицательных свободных членов

для задачи II А' = 

5. Число неравенств  в системе ограничений одной  задачи совпадает с числом  переменных в другой задаче. 
6. Условия неотрицательности переменных имеются в обеих задачах. 
Две задачи I и II линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами. В дальнейшем для простоты будем называть их просто двойственными задачами. 
Исходя из определения, можно предложить следующий алгоритм составления двойственной задачи. 
1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду "<=", а если минимум - к виду ">=". Для этого неравенства, в которых данное требование не выполняется, умножить на -1. 
2. Составить расширенную матрицу системы А₁ в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.  
3. Найти матрицу А'₁, транспонированную к матрице А₁. 
4. Сформулировать двойственную задачу на основании полученной матрицы A'₁ и условия неотрицательности переменных.

Соответствие  переменных
Переменные  исходной задачи
Первоначальные	Дополнительные
Дополнительные	Первоначальные
Переменные  двойственной задачи

2.4. Решение задач с помощью  симплексных таблиц

В этом разделе описано  использование симплексных таблиц для решения задач. Использование симплексных таблиц весьма удобно для ручного расчёта задач. Для заполнения первой симплексной таблицы надо привести систему к каноническому виду. Затем если надо ищется первоначальное допустимое решение или задачу надо решать M-методом. Кроме того, систему представляют в расширенном виде.

(2.19)

Обратите внимание, что  коэффициенты при переменных в функции  меняют знак! Все введённые переменные имеют тот же знак, что и свободные  члены иначе надо использовать M-метод (или заранее отыскать ПДБР). Далее эти данные заносятся в первую симплексную таблицу, общий вид которой представлен ниже.

Базис	Свободный член	Переменные							Оценочное отношение
		x1	...	xj	...	xs	...	xn+m
x1	b1	a11	...	a1j	...	a1s	...	a1n+m	g1
...	...	...	...	...	...	...	...	...	...
xi	bi	ai1	...	aij	...	ais	...	ain+m	gi
...	...	...	...	...	...	...	...	...	...
xq	bq	aq1	...	aqj	...	aqs	...	aqn+m	gq
...	...	...	...	...	...	...	...	...	...
xm	bm	am1	...	amj	...	ams	...	amn+m	gm
F	c0	c1	...	cj	...	cs	...	cn+m	MAX/MIN

(2.20)

 

Теперь, поясним, что есть что. Каждая строка - это уравнение  в расширенной системе (смотрите формулу 2.19). В столбце "Базис" перечисляются все базисные (основные) переменные, их число равно числу уравнений в системе ограничений. Следующий столбец, "Свободные член" заполняется значениями свободных членов уравнения. В самую верхнюю строку (под надписью "переменные") выписываются все переменные. Самая нижняя строка, начиная с c₁, заполняется значениями коэффициентов при переменных, которые написаны вверху таблицы, из уравнения функции (с обратным знаком, как в расширенной системе), если в уравнении функции такой переменной нет, то пишем ноль. Ячейки "a" заполняются так. Если вверху столбца написана основная переменная, то на пересечении этого столбца со строкой, в которой написана та же переменная ставим 1, во все остальные ячейки столбца пишем 0. Если же вверху столбца неосновная переменная, то в ячейки записываются её коэффициенты из соответствующего уравнения, если её нет в этом уравнении, то пишем 0. В ячейку c₀, на первом шаге просто пишем ноль.

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

Если решение не оптимально, ищем разрешающий столбец (индекс s), он определяется коэффициентом при переменной в уравнении функции, то есть нижней строкой начиная c₁. Для задачи на минимум это любой столбец, где c максимальный, положительный элемент, а для задачи на максимум, минимальный, отрицательный элемент. Далее проводим расчёт оценочных отношений и заполняем соответствующий столбец. Расчет производится в соответствии со следующим правилом:

• если b_i и a_is имеют разные знаки, то g_i равно бесконечности
• если b_i равно нулю и a_is меньше нуля, то g_i равно бесконечности
• если b_i равно нулю и a_is больше нуля, то g_i равно нулю
• если a_is равно нулю, то g_i равно бесконечности
• иначе g_i равно частному от деления b_i на a_is

После того, как столбец  с g заполнен. Выбирается разрешающая строка (индекс q). Это строка, в которой самое минимальное оценочное отношение (но не ноль и не бесконечность). На пересечении разрешающих строки и столбца находится разрешающий элемент - a_qs.

Теперь составляется новая  таблица. В столбце "Базис" вместо старой переменной - 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, операции  с файлами, написание материалов.

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

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

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

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

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

Сайт model.scc.

Б.Я Советов, С.А. Яковлев. Моделирование  систем. М. Высшая школа,1985

Ю.М. Коршунов. Математические основы кибернетики .М.Энергоатомиздат,1987

А.А. Горчаков, И.В. Орлова. Компьютерные экономико-математические модели.М.ЮНИТИ,1995

А.Н. Колесников. Краткий курс математики для экономистов.М.ИНФА-М,1997

В.И. Бережной, Е.В. Бережная Экономико-математические методы и модели в примерах и задачах. Ставрополь,1996

Экономико-математические методы и  прикладные модели. М.Финстатинформ,1997

Б.Я Советов, С.А. Яковлев. Моделирование систем. Практикум. М. Высшая школа,1999

С.И. Шелобаев. Математические методы и модели. М. Юнити, 2000

В.А. Абчук. Экономико-математические методы. Санкт-Петербург Союз,1999

О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемных. Математические методы в экономике. М.ДИС, 1997.