Решение целочисленной задачи линейного программирования

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. Постановка линейной целочисленной задачи

2. Описания метода отсекающих плоскостей

2.1 Идея метода

2.2 Дробный алгоритм решения полностью целочисленных задач

2.3 Эффективность отсечения Гомори

3. Использование метода отсекающих плоскостей для решения одной задачи линейного целочисленного программирования

4. Сравнение вычислительных возможностей метода отсекающих плоскостей и метода ветвей и границ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

Приложение 1. Листинг программы

Приложение 2. Результат работы программы

ВВЕДЕНИЕ

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

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

Рассмотрим в этой работе один из методов отсечения, разработанный Р. Гомори, который называется методом отсекающих плоскостей. Он включает в себя дробный алгоритм, который используется при решении полностью целочисленных задач, а также алгоритм решения частично целочисленных задач, в силу своей специфики в данной работе не разбирающийся.

1. ПОСТАНОВКА ЛИНЕЙНОЙ ЦЕЛОЧИСЛЕННОЙ ЗАДАЧИ

Среди совокупности п неделимых предметов, каждый i-ый (i=1,2, ... , п) из которых обладает по j-ой характеристике показателем и полезностью , найти такой набор, который позволяет максимизировать эффективность использования ресурсов величины .

Математическая модель этой задачи может быть представлена следующим образом:

в области, определенной условиями

(1)

(2)

- целые, . (3)

найти решение , при котором максимизируется (минимизируется) значение целевой функции

(4)

Если , то (1-4) является моделью частично целочисленной задачи.

Но нас будет интересовать случай, когда , то есть когда (1-4) является моделью полностью целочисленной задачи.

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

Вектор , удовлетворяющий условиям (1-3), называется допустимым решением задачи (1--4). Допустимое решение, при котором функция (4) достигает наибольшего (наименьшего) значения, называется оптимальным решением.

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

Рассмотрим следующий пример. В области, определенной условиями

-целые

найти максимум функции .

Решим задачу геометрически (рис. 1). Область поиска экстремума-- многоугольник ODABC, но так как линия уровня целевой функции параллельна стороне АВ многоугольника, экстремум достигается в вершинах и , а также в любой точке отрезка АВ, и равен 7.



(рис. 1)

Однако нас интересуют лишь точки с целочисленными координатами, следовательно, ни А, ни В не являются допустимым решением задачи. Округляя значение координат А, получим Но точка А' не принадлежит области поиска. Можно показать, что целочисленный оптимум достигается в точках N(3; 2) и M(2; 3) и равен 5. Обе точки внутри области поиска.

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

2. ОПИСАНИЕ МЕТОДА ОТСЕКАЮЩИХ ПЛОСКОСТЕЙ

2.1 Идея метода

Представленный ниже пример раскрывает смысл понятия “отсекающая плоскость”. Рассмотрим следующую линейную задачу целочисленного программирования:

В области, определенной условиями

,

-целые,

найти максимум функции .

Область допустимых решений задачи с ослабленными ограничениями, получаемой путем отбрасывания требования целочисленности переменных, изображена на рис. 2.1. Оптимальное значение целевой функции z=63 достигается в точке с дробными координатами .

(рис 2.1)

В основе метода отсекающих плоскостей лежит преобразование области допустимых решений задачи с ослабленными ограничениями в выпуклый многогранник, экстремальная точка которого является оптимальным решением исходной целочисленной задачи. При этом, естественно, все допустимые целочисленные решения исходной задачи должны лежать внутри или на границе построенного многогранника. На рис. 2.1 показано, как введение двух (некоторым образом выбранных) дополнительных ограничений позволяет получить новую экстремальную точку с координатами (4,3), являющуюся оптимальным решением сформулированной выше задачи целочисленного программирования. Заметим, что область, отсеченная от множества допустимых решений ослабленной задачи, не содержит точек с целочисленными координатами (на рис. 2.1 эта область заштрихована).

Ниже рассмотрим, каким образом строятся дополнительные ограничения для полностью целочисленных задач.

2.2 Дробный алгоритм решения полностью целочисленных задач

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

можно записать в виде неравенства

в котором дроби отсутствуют. Последнее неравенство получено путем умножения обеих частей рассматриваемого ограничения на наименьший общий знаменатель входящих в него коэффициентов.

Необходимость введения требования целочисленности параметров исходной задачи обусловлена следующими соображениями. Из дальнейшего рассмотрения будет видно, что как исходные, так и дополнительные переменные задачи, решаемой с помощью дробного алгоритма, должны быть целочисленными. Между тем наличие в ограничениях дробных коэффициентов приводит к нарушению целочисленности дополнительных переменных. В этом случае дробный алгоритм позволяет обнаружить отсутствие допустимого решения даже тогда, когда задача, записанная в исходных переменных, имеет допустимое целочисленное решение.

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

Базисные переменные	Решение (свободные члены)	Свободные переменные
		. . . . . .
z		. . . . . .
. . . . . .	. . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Здесь через обозначены базисные переменные, а через - небазисные (свободные) переменные. Такая структура обозначений выбрана из соображений удобства.

Рассмотрим i-ю строку симплексной таблицы, которой соответствует нецелое значение базисной переменной , и выразим через небазисные переменные:

нецелое. (1)

Каждую строку симплексной таблицы, порождающую аналогичное равенство, будем называть производящей строкой. Так как коэффициенты целевой функции можно считать целыми числами, переменная z также должна быть целочисленной, и верхнюю строку таблицы допустимо выбирать в качестве производящей. Кроме того, требование целочисленности z оказывается весьма существенным при доказательстве конечности рассматриваемого алгоритма. Пусть

(2)

где N=[a] -- наибольшее целое число, удовлетворяющее условию Na. Отсюда следует, что a-[a]0.

Тогда число = имеет следующие ограничения:

1) (равенство нулю невозможно, так как -нецелое и )

2) (Так как наиближайшее целое к )

Аналогично на число = накладываются неравенства:

1) (равенство нулю возможно, так как коэффициенты в результате использования симплекс-метода вполне могут оказаться целыми, т.е. )

2) .

Таким образом, -есть положительная дробь, а неотрицательная дробь. После подстановки приведенных выше тождеств (2) в (1) уравнение, выражающее через небазисные переменные, приобретает следующий вид:

или

Поскольку все переменные и принимают целые значения, правая часть уравнения должна быть целочисленной, откуда следует, что левая часть уравнения также должна принимать целые значения. Далее, так как и для всех i и j, то . Следовательно, выполняется неравенство

.

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

Последнее ограничение перепишем в виде равенства

или ,

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

Преобразуем исходную таблицу путем приписывания к ней строки и столбца, соответствующих построенному отсечению Гомори для полностью целочисленной задачи. Получим новую таблицу:

Базисные переменные	Решение (свободные члены)	Свободные переменные
		. . . . . .
Z		. . . . . .
. . . . . .	. . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
		. . . . . .

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

Название дробный алгоритм связано с тем обстоятельством, что все ненулевые коэффициенты введенного отсечения меньше единицы.

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

Дробный алгоритм имеет два недостатка.

1. Ошибки округления, возникающие в процессе вычислений с помощью ЭВМ, в ряде случаев приводят к получению неверного (неоптимального) целочисленного решения. Трудности такого рода можно избежать путем раздельной записи в памяти ЭВМ числителей и знаменателей различных дробей (и, следовательно, исключить оперирование десятичными дробями). Однако количество разрядов в указанных целых числах может превысить возможности запоминающего устройства компьютера.

2. Решения, последовательно получаемые в процессе реализации алгоритма, не являются допустимыми, т. е. алгоритм не позволяет получить какое-либо целочисленное решение, отличное от оптимального.

Это означает, что в случае вынужденного прекращения вычислений до момента окончания процесса решения в памяти ЭВМ не будет никакого «приемлемого» целочисленного решения исходной задачи.

2.3 Эффективность отсечения Гомори

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

Рассмотрим неравенства

, (1)

. (2)

Будем говорить, что отсечение (1) более эффективно, чем отсечение (2), если и для всех j, причем по крайней мере в одном случае выполняется строгое неравенство.

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

3. ИСПОЛЬЗОВАНИЕ МЕТОДА ОТСЕКАЮЩИХ ПЛОСКОСТЕЙ ДЛЯ РЕШЕНИЯ ОДНОЙ ЗАДАЧИ ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

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

В области, определенной условиями

,

-целые,

найти максимум функции .

Решение.

Запишем задачу в стандартном виде. Введем дополнительные переменные .

При этом будем находить минимум функции =-z, равный максимуму целевой функции z.

-целые.

После применения симплекс-метода для этой же задачи, но с ослабленными ограничениями, получаемой путем отбрасывания требования целочисленности переменных, имеем из исходной симплекс-таблицы следующую:

Базисные переменные	Решение (свободные члены)	Свободные переменные
L	-	-	-
Базисные переменные	Решение (свободные члены)	Свободные переменные
L	0	2	3
	11	3	-1
	6	-2	3

линейный целочисленный задача отсекающий часть

Оптимальное значение целевой функции z= достигается в точке с дробными координатами .

Для определения наиболее эффективного отсечения воспользуемся вторым эмпирическим. То есть отсечение будем строить на основе производящей i-ой строки, которой соответствует

.

Чтобы применить это правило, необходимо вычислить все коэффициенты отсечения Гомори для каждой из производящих строк. Введем отсечения, соответствующие производящим строкам с базисными переменными и целевой функции L:

 (L-строка)

(-строка)

(-строка)

; ; .

Так как (имеем 2 максимальных отношения) воспользуемся дополнительно первым эмпирическим правилом. Для этого найдем:

.

Делаем вывод, что в качестве производящей строки следует выбрать строку с базисной переменной

: ; ; .

Следовательно уравнение отсечения Гомори имеет вид

.

Получаем новую таблицу:

Базисные перемен- ные	Решение (свободные члены)	Свободные переменные
L	-	-	-

Так как решение оптимально, но недопустимо(базисная переменная ), то необходимо применить двойственный симплекс-метод, который обеспечивает выполнение условия оптимальности решения и одновременно систематическое приближение его к области допустимых решений.

В качестве разрешающей строки берется строка с наибольшей по абсолютной величине отрицательной базисной переменной. В нашем случае на каждом шаге такая строка всегда будет одна(с добавляемой переменной ).

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

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

Вернемся к примеру.

За разрешающую, очевидно, берем -строку.

Найдем следующие отношения:

; .

Так как второе отношение меньше, чем первое, то в качестве разрешающего столбца берем второй (-столбец).

Далее проводим обычное преобразование строк симплекс-таблицы.

Получаем

Базисные перемен-ные	Решение (свободные члены)	Свободные переменные
L	-	-	-
	5	0	1
			-

Так как решение нецелочисленное, то опять проводим отсечение на основе производящей строки с переменной :

Добавляемая строка имеет следующий вид

	-	-	-

После применения двойственного симплекс-метода таблица примет окончательный вид.

Базисные перемен-ные	Решение (свободные члены)	Свободные переменные
L	-25	-2	-3
	5	1	0
	5	0	1
	1	2	-3
	1	-3	1

Таким образом, имеем следующее решение: при достигается максимум функции z=25.

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

Так как

,

То первое отсечение будет выглядеть так:

или .

Это уравнение эквивалентно неравенству .

Аналогичным образом второе отсечение порождает эквивалентное ограничение в переменных и :



или .

Значит .

Изобразим на графике, как введение этих двух ограничений позволяет получить новую экстремальную точку с координатами A(5,5).

(рис 3)

4. СРАВНЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ВОЗМОЖНОСТЕЙ МЕТОДА ОТСЕКАЮЩИХ ПЛОСКОСТЕЙ И МЕТОДА ВЕТВЕЙ И ГРАНИЦ

Попробуем охарактеризовать поведение алгоритмов метода отсекающих плоскостей и метода ветвей и границ при решении задач целочисленного линейного программирования. В качестве меры продолжительности вычислений рассмотрим количество симплексных итераций I и количество дополнительных линейных ограничений D.

Сравним выше указанные методы при решении следующей целочисленной задачи:

В области, определенной условиями

,

-целые,

найти максимум функции .

Получили следующие результаты.

При использовании метода отсекающих плоскостей (см. приложение 2):

x[1]=1 (погрешность 1.788139e-07)

x[2]=1 (погрешность 5.960464e-07)

x[3]=8 (погрешность 1.000000e-16)

x[4]=0 (погрешность 1.000000e-16)

Максимум функции z=101.

Количество симплексных итераций: I=5

Количество дополнительных ограничений: D=1

При использовании метода ветвей и границ:

x[1]=1 (погрешность 5.960464e-08)

x[2]=1 (погрешность 5.960464e-08)

x[3]=8 (погрешность 1.000000e-16)

x[4]=0 (погрешность 1.000000e-16)

Максимум функции z=101.

Количество симплексных итераций: I=12

Количество дополнительных ограничений: D=4

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

Но следует обратить внимание на погрешность полученных результатов.

Во втором случае для переменных она на порядок ниже.

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

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

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

Изложим отдельные свойства алгоритма, реализующего метод отсекающих плоскостей.

Числа I и D имеют (в среднем) тенденцию к возрастанию с увеличением числа переменных и ограничений, ростом порядка коэффициентов задачи и увеличением заполненности матрицы .

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

Не удается установить непосредственную связь между размерами задач (т. е. числом ограничений m и переменных n) и числом итераций: неудачи были зафиксированы даже для небольших задач (m?10, n?10), а успехи -- для задач достаточно большого размера (m = 215, n = 2600).

Наконец, имеет место немонотонность приближения допустимого решения к оптимальному -- при каждом вводимом новом отсечении ?() не обязательно уменьшается и лишь на последней итерации обязательно становится равным нулю.

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

ЗАКЛЮЧЕНИЕ

В данной работе был рассмотрен метод отсекающих плоскостей и представлена программа на языке программирования С++, реализующая данный метод.

Также приведен конкретный пример решения полностью целочисленной задачи выше указанным методом. При этом использовались условия наиболее эффективного отсечения. В результате было введено два дополнительных ограничения и после чего получен целочисленный ответ.

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Таха Х., Введение в исследование операций: В 2-х книгах. Кн. 1. М.: Мир, 1985. 479с.

2. Подбельский В. В. и Фомин С. С. Программирование на языке Си. М.: “Финансы и статистика”, 2000. 599с.

3. Лященко И.Н. Линейное и нелинейное программирование, М.: Наука, - 1985.

4. Санович К.М. Исследование операций, М.: Наука, - 1989.

Листинг программы

#include<stdio.h>

#include<iostream.h>

#include<conio.h>

#include<math.h>

void main()

{

float dr(float);

float zz,*x,**a,alk,*ai,*aj,**f;

int simpiter=0,p,n=4,m=4,i=0,j=0,k=0,l=0,q=0,xx;

clrscr();

x=new float[m+1];//m - k-vo peremennyh

ai=new float[n+m+100];

aj=new float[m+n+100];

a=new float*[n+m+100];

for(i=0;i<n+m+100;i++)

{

a[i]=new float[m+1];

}

f=new float*[n+m+1];

for(i=0;i<n+1;i++)

{

f[i]=new float[m+1];

}

/* a[0][0]=0; a[0][1]=2;a[0][2]=3;

a[1][0]=11; a[1][1]=3;a[1][2]=-1;

a[2][0]=6; a[2][1]=-2;a[2][2]=3;*/

a[0][0]=0; a[0][1]=2;a[0][2]=3; a[0][3]=12;a[0][4]=3;

a[1][0]=13; a[1][1]=4;a[1][2]=1; a[1][3]=1;a[1][4]=1;

a[2][0]=17; a[2][1]=-2;a[2][2]=-3; a[2][3]=1;a[2][4]=1;

a[3][0]=15; a[3][1]=-2;a[3][2]=1; a[3][3]=2;a[3][4]=2;

a[4][0]=18; a[4][1]=2;a[4][2]=4; a[4][3]=-1;a[4][4]=1;

for(i=0;i<n+1;i++)

{

for(j=0;j<m+1;j++)

cout<<a[i][j]<<' ';

cout<<'\n';

}

for(i=1;i<=m;i++)

x[i]=i;

i=1;

while(i<n+1)

{

if(a[i][0]<0)

{

for(j=1;j<m+1;j++)

{

if(a[i][j]>=0) q++;

else {

k=j;

break;

}

}

if(q==m) goto A;

else

{

j=i;

zz=a[i][0]/a[i][k];

for(l=1;l<n+1;l++)

if((a[l][0]/a[l][k]>0)&&(zz>(a[l][0]/a[l][k])))

{

zz=a[l][0]/a[l][k];

j=l;

}

alk=a[j][k];

l=j;

for(xx=1;xx<m+1;xx++)

{

if(x[xx]==k) {

x[xx]=l*10;

continue;

}

if(x[xx]==10*l) {

x[xx]=k;

continue;

}

}

simpiter++;

alk=a[i][k];

l=i;

for(j=0;j<m+1;j++)

ai[j]=a[l][j];

for(j=0;j<n+1;j++)

aj[j]=a[j][k];

for(i=0;i<n+1;i++)

for(j=0;j<m+1;j++)

a[i][j]=a[i][j]+ai[j]*(-aj[i])/alk;

for(j=0;j<m+1;j++)

a[l][j]=ai[j]/alk;

for(j=0;j<n+1;j++)

a[j][k]=-aj[j]/alk;

a[l][k]=1/alk;

}

for(i=0;i<n+1;i++)

{

for(j=0;j<m+1;j++)

cout<<a[i][j]<<' ';

cout<<'\n';

}

i=0;

}

i++;

}

j=1;

while(j<m+1)

{

if(a[0][j]>0)

{

q=0;

for(i=1;i<n+1;i++)

{

if(a[i][j]<=0) q++;

else {

k=i;

break;

}

}

if(q==n) goto C;

else

{

i=k;

for(l=1;l<n+1;l++)

if((a[l][j]>0)&&(a[l][0]>0)&&((a[i][0]/a[i][j])>(a[l][0]/a[l][j])))

i=l;

l=i;

k=j;

for(xx=1;xx<m+1;xx++)

{

if(x[xx]==k) {

x[xx]=l*10;

continue;

}

if(x[xx]==10*l) {

x[xx]=k;

continue;

}

}

simpiter++;

alk=a[i][k];

for(j=0;j<m+1;j++)

ai[j]=a[l][j];

for(j=0;j<n+1;j++)

aj[j]=a[j][k];

for(i=0;i<n+1;i++)

for(j=0;j<m+1;j++)

a[i][j]=a[i][j]+ai[j]*(-aj[i])/alk;

for(j=0;j<m+1;j++)

a[l][j]=ai[j]/alk;

for(j=0;j<n+1;j++)

a[j][k]=-aj[j]/alk;

a[l][k]=1/alk;

}

j=0;

}

j++;

}

for(p=1;;p++)

{

q=1;

for(xx=1;xx<m+1;xx++)

{

if (fabs(dr(a[int(x[xx]/10)][0]))<0.001) q++;

}

if (q==m+1) break;

alk=0;

for(xx=1;xx<m+1;xx++)

if((x[xx]>=10)&&(dr(a[int(x[xx]/10)][0])>=alk))

{

alk=dr(a[int(x[xx]/10)][0]);

q=int(x[xx]/10);

}

cout<<"\n"<<alk<<" "<<q<<"\n";

for(j=1;j<m+1;j++)

{

a[n+p][j]=-dr(a[q][j]);

}

a[n+p][0]=-alk;

alk=1000000;

for(j=1;j<m+1;j++)

if ((a[n+p][j]<0)&&(a[0][j]/a[n+p][j]<alk))

{

alk=a[0][j]/a[n+p][j];

k=j;

}

l=n+p;

for(i=0;i<n+p+1;i++)

{

for(j=0;j<m+1;j++)

cout<<a[i][j]<<' ';

cout<<'\n';

}

for(xx=1;xx<m+1;xx++)

{

if(x[xx]==k)

{

x[xx]=l*10;

continue;

}

}

alk=a[l][k];

simpiter++;

for(j=0;j<m+1;j++)

ai[j]=a[l][j];

for(j=0;j<n+p+1;j++)

aj[j]=a[j][k];

for(i=0;i<n+p+1;i++)

for(j=0;j<m+1;j++)

a[i][j]=a[i][j]+ai[j]*(-aj[i])/alk;

for(j=0;j<m+1;j++)

a[l][j]=ai[j]/alk;

for(j=0;j<n+p+1;j++)

a[j][k]=-aj[j]/alk;

a[l][k]=1/alk;

cout<<"\n";

}

for(i=0;i<n+p;i++)

{

for(j=0;j<m+1;j++)

cout<<a[i][j]<<' ';

cout<<'\n';

}

for(xx=1;xx<m+1;xx++)

{

if(x[xx]<10) printf("\n x[%d]=0 погрешность=0.000000e+00",xx);

if(x[xx]>=10) printf(" \n x[%d]=%d погрешность=%e", xx, int

(a[int(x[xx]/10)][0]+0.1) ,a[int(x[xx]/10)][0]-

int(a[int(x[xx]/10)][0]+0.1));

}

cout<<"\n Максимум функции z="<<-a[0][0];

cout<<"\n Количество симплексных итераций: I="<<simpiter;

cout<<"\n Количество дополнительных ограничений: D="<<p-1;

goto B;

A:

cout<<"net dopustimih resheniy";

goto B;

C:

cout<<"net optimalnih resheniy";

B:

getch();

}

float dr(float y)

{

float y1;

if (y>=0) y1=y-int(y+0.00001);

else y1=y-int(y-0.00001)+1;

if (fabs(y1-1)<0.00001) y1=0;

return y1;

}

Результат работы программы

x[1]=1 (погрешность 1.788139e-07)

x[2]=1 (погрешность 5.960464e-07)

x[3]=8 (погрешность 1.000000e-16)

x[4]=0 (погрешность 0.000000e-16)

Максимум функции z=101.

Количество симплексных итераций: I=5

Количество дополнительных ограничений: D=1

Размещено на Allbest.ru