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

Normal;

1

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

ВВЕДЕНИЕ

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

В данном ПЗ описывается программа, написанная в соответствии с постановкой задачи на курсовое проектирование по теме "Решение линейной задачи табличным симплекс методом" по дисциплине "Методы исследования операций". Данная программа предназначена для быстрого решения линейной задачи, позволяющей определить план производства изделий, обеспечивающий максимальную прибыль от его реализации. Для проверки работы программы разработан тестовый пример. Результаты тестирования доказывают, что программа правильно выполняет все операции по обработке входных данных и формирования выходных данных.

Область применения программы - различные экономические предприятия, где необходимо оптимально распределить время для выполнения тех или иных работ.

1. ОБЗОР АЛГОРИТМОВ МЕТОДОВ РЕШЕНИЯ ЗЛП

Задачи линейного программирования могут решаться с помощью следующих алгоритмов:

--Графический метод

--Табличный симплекс метод

--Метод искусственного базиса

--Модифицированный симплекс метод

--Двойственный симплекс метод

1.1 Графический симплекс метод

Метод используется при любых ограничениях и числом переменных не более трех. Алгоритм метода:

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

Строится "нормаль"- линия, соединяющая начало координат с точкой, координаты которой задаются соответствующими коэффициентами целевой функции. Вдоль нормали мысленно перемещается перпендикуляр. Если задача решается на MIN, то перемещение осуществляется от начала координат к точке, если на MAX, то от точки к началу координат.

Пересечение перпендикуляра с крайней точкой областью ограничения и есть решение задачи.

Замечание к методу:

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

2. Если система ограничений несовместна, то задача решений не имеет.

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

1.2 Метод искусственного базиса (искусственных переменных)

Используется при любых ограничения и любом количестве переменных. Алгоритм метода:

Задача приводится к канонической форме.

В те равенства, в которые дополнительные переменные вводились со знаком (-) добавляются искусственные переменные.

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

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

1.3 Модифицированный симплекс метод

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

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

1.4 Двойственный симплекс метод

Смысл двойственной задачи - производственная и экономическая области. Если прямая задача решается на Max, то двойственная решается на Min. Коэффициенты целевой функции прямой задачи становятся векторами свободных членов системы ограничений двойственной задачи. Столбец свободных членов системы ограничений прямой задачи становятся вектором коэффициентов целевой функции двойственной задачи.

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

Алгоритм решения:

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

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

В соответствии с расширенной системой ограничений строится двойственная задача.

Подбирается сопряженный базис, отыскивается псевдоплан.

Если оказалось, что в разложении Ао все элементы положительны, то мы получили оптимальный план, и это решение представлено в столбце.

Производится цикл пересчета Жордана - Гаусса.

2. Разработка и описание алгоритма ТАБЛИЧНОГО СИМПЛЕКС-МЕТОДА

Симплекс-метод (метод последовательного улучшения плана) впервые был разработан Данцингом в 1947 г. Этот метод позволяет переходить от одного допустимого решения к другому, причём так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритмы симплекс-метода позволяют также установить, является ли задача линейного программирования разрешимой.

Табличный симплекс-метод предназначен для решения задач линейного программирования с ограничениями «?».

Метод включает в себя следующие шаги:

1. Канонизация исходной задачи (мысленное представление её в векторной форме)

Таблица 2.1 - Общий вид симплекс-таблицы

		Сj	C1	…	Cn	0	…	0
Б	Сб	А0	А1	…	Аn	An+1	…	Аn+m
An+1	0	b1	a11	…	a1n	1	…	0
…	…	…	…	…	…	…	…	…
An+m	0	bn	am1	…	amn	0	…	1
	Д	Д0	Д1	…	Дn	…	…	Дn+m

В качестве начального решения при таком подходе становится точка с координатами .

2. Расчёт симплекс разностей по формулам:

,

где - текущее значение целевой функции, оно возрастает при решении задачи на min и убывает при решении на max.

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

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

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

3. Вывод переменной из базиса

Выводимый из базиса вектор выделяется по правилу:

,

где «*» обозначает координаты столбца, вводимого в базис.

В этой ситуации возможны особые случаи:

- Во вводимом столбце нет положительных элементов, что говорит о бесконечном возрастании функции в направлении оптимизации

- В компонентах столбца нет положительных элементов - это означает, что мы имеем дело с несовместной системой ограничений

4. Алгоритм исключений Жордана-Гаусса

В результате исключений Жордана-Гаусса происходит пересчёт матриц и построение новой симплекс-таблицы, после чего алгоритм повторяется с момента расчёта симплекс разностей.

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

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

3. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

Некоторое предприятие занимается производством бетона. Для производства бетона необходимо использовать 3 компонента: песок, щебень, цемент. Дневные ограничения на сырье: песок - 135т, щебень - 150т, цемент - 9т. Для производства одной тонны крупнозернистого и мелкозернистого бетона требуются различные массы материалов, представленные в таблице. Прибыль с продажи 1т крупнозернистого бетона - 5тыс. гривен, с 1т мелкозернистого - 4тыс. гривен. Составить план производства, при котором будет достигнута максимальная прибыли при продажах. Решить задачу симплекс-методом.

Таблица 3.1 - Исходные данные задачи

Сырье	Затраты материала при производстве бетона	Суточный запас компонентов (т)
	мелкозернистого	крупнозернистого
Песок	1	3	135
Щебень	2	3	150
Цемент	2	1	9

4. Экономическая интерпретация

Пусть имеется некое производство, выступающее в качестве преобразователя системы исходных ингредиентов b₁,…,b_m обладающих ценностью, в новую систему носителей ценности - совокупность продуктов. Термины производство, ценность, продукт, а ниже - оценка (как измеритель ценности) будут употребляться в качестве исходных.

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

В основу преобразования ингредиентов положим некоторую конечную совокупность технологических способов, моделируемых векторами , i=1,…,n при этом координаты вектора p_i будем интерпретировать как затраты ингредиентов, приходящиеся на единичную интенсивность (например на единицу времени) использования i-го технологического способа. Саму же интенсивность обозначим через x_i (x_i =1 - единичная интенсивность). Предположим, что затраты ингредиентов и создаваемая ценность подчиняются закону линейной зависимости от вектора интенсивностей. В этом предположении затраты j-го ингредиента, отнесенные к вектору x, выразятся величиной (a_j,x) , i=1,…,m . Так как границы сверху для них определены числами b_j, то должны выполняться неравенства Содержательный смысл вектора x, задающего уровень производства, диктует ограничение x0. Если c_i понимать как оценку ценности, заключенной в носителе конечного результата применения i-го технологического способа с интенсивностью x_i=1, то величина будет выражать суммарную оценку ценности, заключенной в конечных носителях результата преобразования исходных ингредиентов в соответствии с уровнем производства, задаваемым вектором x.

Следовательно, задача max{(c,x)|(a_j,x)b_j, j=1,…,m, x}; решает вопрос об отыскании уровня производства (вектора интенсивностей), подчиненного условиям технологической допустимости (формально - системе линейных неравенств) и доставляющего для (c,x) максимальное значение.

5. Построение математической модели

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

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

х₁ - объем производства мелкозернистого бетона за сутки (в тоннах);

х₂ - объем производства крупнозернистого бетона за сутки (в тоннах).

Целевая функция. Так как стоимость одной тонны бетона каждого вида известна (4 тыс. гривен мелкозернистый и 5 тыс. гривен крупнозернистый), то общий доход от реализации составляет: 4х₁ + 5х₂ (тысяч нривен). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции: определить допустимые значения переменных х₁ и х₂, дающих максимальное значение целевой функции F = 4х₁ + 5х₂.

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

1 х₁ + 2х₂ 135, 2х₁ + 3 х₂ 150, 2 х₁ + 1 х₂ 9.

Неявное ограничение, вытекающее из экономического смысла выбранных переменных, заключается в том, что объемы производства бетона не могут принимать отрицательные значения: х₁ 0, х₂0.

Таким образом, математическую модель задачи можно записать в следующем виде: определить план X = (x₁, х₂), обеспечивающий максимальное значение функции:

Fmax(X) = max (4x ₁ + 5x₂)

при наличии ограничений:

1х₁ + 3х₂ 135,

2х₁ +3х₂ 150,

2х₁ + 1х₂ 9,

х₁ 0, х₂ 0.

6. ВАРИАНТ ЗАДАНИЯ

Найти максимум целевой функции

Fmax(x1,x2)=4x1+5x2

При заданной системе ограничений

1х₁ + 3х₂ 135,

2х₁ +3х₂ 150,

2х₁ + 1х₂ 9,

х₁ 0, х₂ 0.

7. Решение задачи

Каноническая запись исходной задачи:

Fmax(x)= 4x1+5x2+0x3+0x4+0x5

1x1+3x2+1x3+0x4+0x5=135

2x1+3x2+0x3+1x4+0x5=150

2x1+1x2+0x3+0x4+1x5=9

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

Таблица 7.1 - Первая итерация

		Ci	4	5	0	0	0
Б	Сб	А0	А1	А2	А3	А4	А5
А3	0	135	1	3	1	0	0
А4	0	150	2	3	0	1	0
А5	0	9	2	1	0	0	1
		0	-4	-5	0	0	0

Расчёт симплекс разностей по формулам:

,

где - текущее значение целевой функции, оно возрастает с каждой итерацией при решении на максимум.

Выбираем элемент, вводимый в базис, по минимальной симплекс-разности, это А2. Находим элемент, выводимый из базиса, он выбирается по правилу

.

I - номер выводимого элемента, в нашем случае это А5, т.к. min{135/3; 150/3; 9/2}=9/2; Элемент, расположенный на пересечении выводимой (направляющей) строки и вводимого (направляющего) столбца, называется направляющим. Для данной итерации он равен 9/2. Далее делим направляющую строку на направляющий элемент, получается модифицированная строка, которая записывается в новую таблицу на место старой строки. Делим все элементы строки А5, , кроме элемента столбца Сб, на 9/2 и записываем полученные элементы в эту строку. Из оставшихся строк первой таблицы вычитаются элементы модифицированной строки, умноженные на элемент направляющего столбца, стоящий на пересечении с изменяемой в данный момент строкой.

Таблица 7.2 - Вторая итерация

		Ci	4	5	0	0	0
Б	Сб	А0	А1	А2	А3	А4	А5
А3	0	108	-5	0	1	0	-3
А4	0	123	-4	0	0	1	-3
А2	5	9	2	1	0	0	1
		45	6	0	0	0	5

Например: (А3)=135-9*3=108; (А4)=150-9*3=123; Видим, что в таблице нет отрицательных симплекс-разностей, это говорит об окончании решения и отыскания оптимума. Итак, Fmax(x)=45; x1=0; x2=9;

8. Результат вычислительного эксперимента

Введем данные исходной задачи в программу:

Рисунок 7.1 - Начальные данные

Окончательные данные в результате решения:

Рисунок 7.2 - Результаты решения

9. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ

линейный программирование симплекс прибыль

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

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

В процессе анализа модели на чувствительность, необходимо ответить на следующие вопросы:

ь каков статус ресурсов, т.е. какие из них “дефицитные”, а какие “недефицитные”;

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

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

ь как отразится на оптимальном плане увеличение (уменьшение) запаса ресурсов.

В результате решения получим:

Таблица 9.1 - Решенная задача

		C	4	5	0	0	0
Б	Сб	А0	А1	А2	А3	А4	А5
А3	0	108	-5	0	1	0	-3
А4	0	123	-4	0	0	1	-3
А2	5	9	2	1	0	0	1
		45	6	0	0	0	5

Оптимальное решение поставленной задачи -=(0;9) при этом значение целевой функции равно .

Составим двойственную задачу:

Значения переменных , и находятся в строке симплекс - разностей таблицы и равны: = 6, = 5 и = 0.

Оптимальное решение двойственной задачи - , при этом значение целевой функции равно .

9.1 Определение статуса ресурсов

Дефицитными являются первый и второй ресурсы (песок и щебень), так как им соответствует ненулевая оценка: 6 и 5 соответственно. Третий ресурс (цемент) является недефицитным, так как его оценка равна нулю.

9.2 Определение значимости ресурсов

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

9.3 Определение допустимого интервала изменения запаса ресурса

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

Так как начальными базисными переменными являлись х₃, х₄, х₅, то в оптимальной симплексной таблице в соответствующих столбцах расположена матрица А^-1.

Таблица 9.2 - Решенная задача

		C	3	4	0	0	0
Б	Сб	А0	А1	А2	А3	А4	А5
А3	0	108	-5	0	1	0	-3
А4	0	123	-4	0	0	1	-3
А2	5	9	2	1	0	0	1
		45	6	0	0	0	5

Рассчитаем диапазон изменения объемов второго ресурса. Для этого будем изменять величину второго ресурса на величину . Найдём базисное решение, соответствующее измененным запасам первого ресурса:

Решая, получим:

Так как все переменные должны быть не меньше нуля, решим систему неравенств:

Значит , тогда .

Таким образом, первоначальный запас второго ресурса (135 тонн) может быть увеличен до 495 тонн или уменьшен до 10 тонн без нарушения допустимости решения. Уменьшение запаса ресурса в данном примере повлечет за собой уменьшение прибыли от реализации продукции, поэтому является нецелесообразным.

9.4 Исследование зависимости оптимального решения от изменения запасов ресурсов

Будем изменять запасы ресурса, начиная с 135 тонн (начальный запас) с шагом h=2 тонны до 10 тонн. Результаты расчетов приведены в таблице:

Таблица 9.3 - Зависимость функции от параметра b1

	0	2	4	6	8	10
b2	135	205	275	345	425	495
F, тыс.грн.	0	1.4	2.8	4.2	5.6	7
F, тыс.грн.	8,2	8,7	9,2	9,7	10,2	10,7

где - величина, на которую увеличиваем 1 ресурс;

b₁ - свободный член;

F - приращение функции;

F - значение функции.

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

Таблица 9.4 - Зависимость функции от параметра b2

b2	6	6,4	6,8	7,2	7,6	8
	(1/2;5/3)	(2/5;28/15)	(3/10;31/15)	(1/5;34/15)	(1/10;37/15)	(0,8/3)
F, тыс.руб.	8,2	8,7	9,2	9,7	10,2	10,7

Это позволяет сделать вывод, что с увеличением объема запасов щебня на 2 тонны увеличивается выпуск крупнозернистого цемента на 1 тонну, а мелкозернистый не производится вовсе. При этом прибыль от реализации продукции увеличивается на 2,5 тыс.руб.

Построим график зависимости функции от изменения запасов продукта:

F

b2

Рисунок 9.1 - Зависимость функции от параметра b2

10. Описание интерфейса программы

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

Рисунок 10.1 - Исходные данные в программе

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



Рисунок 10.2 - Таблицы и окончательный результат

Выводы и рекомендации по ПРАКТИЧЕСКОМУ использованию реШЕНИЯ

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

Было выяснено, что с увеличением объема запасов щебня на 2 тонны увеличивается выпуск крупнозернистого бетона на 1 тонну и уменьшается выпуск мелкозернистого бетона на 0,5 тонны. При этом прибыль от реализации продукции увеличивается на 2,5 тыс.руб.

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

Библиографический список

1. Зайченко Ю.П. Исследование операций. Издательское объединение «Вища школа», 1975, 320 с.

Карлусов В.Ю., Старобинская Л.П. Методические указания к практическим занятиям по дисциплине «Исследование операций и методы оптимизации» для студентов специальности 7.080401 - «Компьютеризированные системы обработки информации и управления».

Вентцель Е.С. Исследование операций. - М.: Наука, 1980. - 208с

ПРИЛОЖЕНИЕ. Текст программы

#include <iostream.h>

#include <iomanip.h>

#include <conio.h>

#include <string.h>

#include <stdlib.h>

int cVars=0, cUrav=0;

int outB=0, inB=0;

void printmatr();

void calcsimplex();

void printsimplex();

int checksimplex();

int findoutbasis();

void calculating();

class drob //drob - osnovnoi element tablic

{

public:

double ch;

double zn;

drob() {ch=1; zn=1;}

void div(double arg1) //delenie na arg1

{ zn=zn*arg1; }

drob div(drob arg1) //delenie na arg1

{

ch*=arg1.zn;

zn*=arg1.ch;

(*this).s();

return *this;

}

drob mult(drob arg1) //umnovenie na arg1

{

ch*=arg1.ch;

zn*=arg1.zn;

(*this).s();

return *this;

}

drob mult(double arg1) //umnovenie na arg1

{

ch*=arg1;

(*this).s();

return *this;

}

drob min(drob arg1) //vichitanie arg1

{

if(zn!=arg1.zn)

{

double t;

t=zn;

zn*=arg1.zn;

ch=ch*arg1.zn-arg1.ch*t;

(*this).s();

}

else

ch-=arg1.ch;

return *this;

}

drob add(drob arg1) //slovenie arg1

{

if(zn!=arg1.zn)

{

double t;

t=zn;

zn*=arg1.zn;

ch=ch*arg1.zn+arg1.ch*t;

(*this).s();

}

else

ch+=arg1.ch;

return *this;

}

double todouble()

{ return ch/zn; }

void s() //sokrashenie

{

int t=1;

if((int)ch%(int)zn==0)

{

ch=ch/zn;

zn=1;

}

while(t==1)

for(int i=2; ; i++)

{

t=1;

if (((int)zn%i==0) && ((int)ch%i==0))

{ch=ch/i; zn=zn/i; i=1;t=1; }

if ((i>abs(ch))||(i>abs(zn))) { t=0; break; }

}

}

void print() //print prav drob

{

if ((int)ch % (int)zn !=0)

{

if (ch<9&&ch>0)

if (zn<9)

cout<<" "<<ch<<"/"<<zn;

else

if (zn<99)

cout<<" "<<ch<<"/"<<zn;

else

cout<<ch<<"/"<<zn;

else

if(ch<99)

if (zn<9)

cout<<" "<<ch<<"/"<<zn;

else

cout<<ch<<"/"<<zn;

else

cout<<ch<<"/"<<zn;

}

else cout<<setw(5)<<ch/zn;

}

void printnum()

{ cout<<ch/zn; }

};

int* basis,* basisA; //koef basissa and elementi basisa

drob* Cj;

drob** matr;

drob* simplex;

int main()

{

int i,j;

double temp;

char c;

clrscr();

cout<<"Enter count of variables: ";

cin>>cVars;

cout<<"Enter count of Uravneniy: ";

cin>>cUrav;

Cj=new drob[cVars+cUrav+1];

cout<<"Enter koef of targeted function ("<<cVars<<"):"<<endl;

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

{

cin>>temp;

Cj[i].ch=temp;

Cj[i].zn=1;

}

//0 to Cj

for( ; i<=cVars+cUrav; i++)

{

Cj[i].ch=0;

Cj[i].zn=1;

}

//Check Cj

cout<<endl<<"Cj: ";

for(i=1; i<=cVars+cUrav; i++)

{

Cj[i].print();

cout<<" ";

}

//Memory to main table

matr=new drob*[cUrav+1];

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

matr[i]=new drob[cUrav+cVars+1];

//Full mail table 1

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

for(j=0; j<=cUrav+cVars; j++)

{

matr[i][j].ch=0;

matr[i][j].zn=1;

}

//Memory for simplex

simplex=new drob[cVars+cUrav+1];

cout<<endl<<endl<<"Enter matrix of Urav ("<<cVars<<", "<<cUrav<<"):"<<endl;

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

for(j=1; j<=cVars+cUrav; j++)

{

if(j<=cVars)

{

cin>>temp;

matr[i][j].ch=temp;

}

else

if(j==i+cVars) //1 to main diagonal

matr[i][j].ch = 1;

else matr[i][j].ch = 0;

}

cout<<endl<<"Enter koef ("<<cUrav<<"): "<<endl;

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

{

cin>>temp;

matr[i][0].ch=temp;

}

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

{

for(j=1; j<=cVars+cUrav; j++)

{

cout<<matr[i][j].ch<<"X"<<j;

if (j!=cVars+cUrav) cout<<" + ";

}

cout<<" = "<<matr[i][0].ch<<endl;

}

//Make basis

basis = new int[cUrav];

basisA = new int[cUrav];

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

{

basis[i]=0;

basisA[i]=cVars+i;

}

cout<<endl<<"All right (y/n)? ";

c=getch();

clrscr();

if(c=='y') printmatr();

else return 1;

calcsimplex();

printsimplex();

j=0;

while((inB=checksimplex())!=0)

{

j++;

cout<<"Iteration "<<j<<". Continue (y/n)?"<<endl;

c=getch();

if(c=='n') return 1;

clrscr;

outB=findoutbasis();

if (outB<=0)

{

cout<<"I cant find vector to get out from basis. There is no answer!"<<endl;

getch();

return 1;

}

cout<<"To basis - "<<"A"<<inB<<". From basis - "<<"A"<<basisA[outB]<<"."<<endl;

calculating();

cout<<endl;

printmatr();

calcsimplex();

printsimplex();

}

cout<<"We found the answer!"<<endl<<endl;

cout<<"Fmax = "; simplex[0].print();

cout<<endl;

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

if(basis[i]!=0)

{

cout<<"X"<<basisA[i]<<"="<<matr[i][inB].todouble()<<endl;

}

getch();

return 0;

}

void printmatr()

{

int i,j;

for (i=1; i<=cUrav+2; i++)

{

for (j=1; j<=cVars+cUrav+3; j++)

{

if(i==1)

if (j==1||j==2) cout<<"| ";

else

if (j==3) cout<<"| Cj";

else

cout<<"|"<<setw(5)<<Cj[j-3].ch;

else

if(i==2)

if(j==1) cout<<"|BASIS";

else

if(j==2) cout<<"| Cb";

else

cout<<"| "<<'A'<<j-3;

else

{

//Sama matrica

if(j==1)

cout<<"|A"<<setw(4)<<basisA[i-2];

else

if(j==2) cout<<"|"<<setw(5)<<basis[i-2];

else

{

cout<<"|"; matr[i-2][j-2-1].print();

}

}

}

cout<<"|"<<endl;

}

}

void calcsimplex()

{

int i,j;

drob temp;

for(i=0; i<=cUrav+cVars; i++)

{

simplex[i].ch=0;

simplex[j].zn=1;

}

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

for (j=0; j<=cUrav+cVars; j++)

{

temp=matr[i][j];

temp.mult(basis[i]);

simplex[j].add(temp);

}

for(j=1; j<=cUrav+cVars; j++)

simplex[j].min(Cj[j]);

}

void printsimplex()

{

int i;

cout<<"| |sig ";

for(i=0; i<=cUrav+cVars; i++)

{

cout<<'|';

simplex[i].print();

}

cout<<"|"<<endl<<endl;;

}

int checksimplex()

{

int i, imax=0;

double max=0;

for(i=1; i<=cVars+cUrav; i++)

if(simplex[i].todouble()<0)

if (simplex[i].todouble()<max)

{

imax=i;

max=simplex[i].todouble();

}

if (imax!=0)

{

cout<<endl<<"Most big simplex < 0 - ";

simplex[imax].print();

cout<<endl;

}

return imax;

}

int findoutbasis()

{

int i, imin=0;

double min=99999;

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

if(matr[i][inB].ch!=0)

if((matr[i][inB].todouble()>0) && (abs(matr[i][0].todouble()/matr[i][inB].todouble())<min))

{

min=matr[i][0].todouble()/matr[i][inB].todouble();

imin=i;

}

return imin;

}

void calculating()

{

int i, j;

drob temp=matr[outB][inB];

drob t2;

//Change Basis

basis[outB]=Cj[inB].ch;

basisA[outB]=inB;

//Pereschet napr stroki

for(j=0; j<=cUrav+cVars; j++)

matr[outB][j].div(temp);

//Pereshet ostalnogo

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

if (i!=outB)

temp=matr[outB][j];

temp.mult(t2);

matr[i][j].min(temp);

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