Разработка проекта решения оптимизационной задачи распределения времени рекламы между радио и телевидением

1. Постановка задачи оптимизации

2. Базовая аналитическая модель

3. Обоснование выбора математических методов решения оптимизационной задачи

4. Решение задачи оптимизации

4.1 Алгоритмы решения задачи

4.2 Описание проекта

5. Испытание модели на чувствительность Заключение Список использованных источников Приложение

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

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

Исследование операций начинается тогда, когда для обоснования решений применяется тот или другой математический аппарат. Цель исследования операций — предварительное количественное обоснование оптимальных решений с опорой на показатель эффективности. Любая задача, которая решается, должна рассматриваться с точки зрения влияния на критерии функционирования системы в целом. Для исследования операций характерно то, что при решении каждой проблемы могут возникать новые задачи. Важной особенностью исследования операций есть стремление найти оптимальное решение поставленной задачи (принцип «оптимальности»). Однако на практике такое решение найти невозможно по таким причинам:

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

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

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

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

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

Задачи Линейного программирования являются математическими моделями многочисленных задач технико-экономического содержания. Характерным примером прикладных задач линейного программирования является транспортная задача.

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

Целью данного курсового проекта является максимизации эффективности использования средств на рекламу продукции.

Данный курсовой проект выполнен в среде программирования NetBeans IDE 7.2. Проверка правильности решения выполнена в среде MS Excel.

1. Постановка задачи оптимизации

Фирма имеет возможность рекламировать свою продукцию, используя местные радио и телевизионную сети. Затраты на рекламу в бюджете фирмы ограничены величиной 1000 $ в месяц. Каждые 60 секунд радиорекламы обходится в 5 $, а каждые 60 секунд телерекламы — в 100 $. Фирма хотела бы использовать радиосеть по крайне мере в два раза чаще, чем сеть телевидения, а так же приобрести время для рекламы на телевидении не менее 300 секунд. Из опыта известно, что объем сбыта продукции, который обеспечивают каждые 60 секунд телерекламы, в 25 раз больше сбыта, обеспечиваемого 60 секундами радиорекламы.

2. Базовая аналитическая модель

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

Для построения математической модели задачи введем переменные:

· обозначим через вектор количество секунд рекламы в месяц: — время рекламы на радио, — время рекламы на TV.

· Затраты на рекламу по радио составляют, а затраты на телевизионную рекламу

Составим ограничение на расход средств:

Ограничение на затраты на рекламу ($):

Ограничение на использование радио рекламы (сек):

Ограничение на использование телевизионной рекламы (сек):

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

Приведем полную математическую модель рассматриваемой задачи:

3. Обоснование выбора математических методов решения оптимизационной задачи

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

Идея метода проста и заключается в следующем. По определенному правилу находится первоначальный опорный план (некоторая вершина области ограничений). Проверяется, является ли план оптимальным. Если да, то задача решена. Если нет, то переходим к другому улучшенному плану — к другой вершине. значение целевой функции на этом плане (в этой вершине) заведомо лучше, чем в предыдущей. Алгоритм перехода осуществляется с помощью некоторого вычислительного шага, который удобно записывать в виде таблиц, называемых симплекс-таблицами. Так как вершин конечное число, то за конечное число шагов мы приходим к оптимальному решению.

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

Поиск решения на основе симплекс-метода в форме симплекс-таблиц имеет следующие этапы:

1. Запись задачи в симплекс-таблицу.

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

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

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

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

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

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

Он имеет следующие преимущества:

1. Простота.

2. Эффективность вычислительной процедуры.

3. Меньшее количество вычислительных операций.

4. Меньший объем памяти ЭВМ.

Поиск решения на основе модифицированного симплекс-метода имеет следующие этапы:

1.

Введение

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

2. Поиск оптимального решения на основе целевой функции.

4. Решение задачи оптимизации

4.1 Алгоритмы решения задачи

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

Определим минимальное значение целевой функции:

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

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

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

В составленной нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю — это элемент: -300, он задает ведущую строку — X5. В этой строке так же находим максимальный по модулю отрицательный элемент: -1 он находится в столбце X2 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответствующая ведущему столбцу включается в базис. Пересчитаем симплекс-таблицу:

В составленной нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю — это элемент: -600, он задает ведущую строку — X4. В этой строке так же находим максимальный по модулю отрицательный элемент: -1 он находится в столбце X1, который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответствующая ведущему столбцу включается в базис. Пересчитаем симплекс-таблицу:

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. В строке F имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент — это -27 Ведущей строкой будет та, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X3, а ведущий элемент: 1.833.

Так как в строке F нет отрицательных элементов, то найдено оптимальное решение: F=14 722, при значениях переменных равных: X1=1092, X2=545.

Решим прямую задачу линейного программирования модифицированным симплексным методом

Определим максимальное значение целевой функции F (X) = x₁+25x₂ при следующих условиях — ограничениях.

0.083x₁+1.667x₂?1000

x₁-2x₂?0

x₂?300

0.083x₁ + 1.667x₂ + 1x₃ + 0x₄ + 0x₅ = 1000

1x₁-2x₂ + 0x₃-1x₄ + 0x₅ = 0

0x₁ + 1x₂ + 0x₃ + 0x₄-1x₅ = 300

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

Матрица коэффициентов A = a_ij

Матрица b.

Итерация № 1.

Базисные переменные: = (3, 6, 7)

Матрица C:

C = (0, 0, 0, 0, 0, 1, 1)

C_{B (3,6,7)} = (0, 1, 1)

C_{N (1,2,4,5)} = (0, 0, 0, 0)

Матрица N формируется из матрицы, А из соответствующих столбцов с номерами N.

Вычисляем:

u = C_BB^-1 = (0, 1, 1)

Умножаем вектор u на матрицу N: uN = (1, -1, -1, -1)

C^* = C_N — uN = (-1, 1, 1, 1)

Откуда номер направляющего столбца s = 1 (индекс максимального по модулю значения из отрицательных элементов).

a^* = B^-1 (a₁₁,…, a_m1)^T = (0.083, 0, 0)^T

min (1000:0.083 = 12 048.19;0:1 = 0;-;) = 0

Откуда номер направляющей строки r = 2 (индекс минимального значения).

Итерация № 2.

Матрица C.

C = (-1, 1, 0, 1, 1, 0, 0)

a^* = B^-1 (a₁₁,…, a_m1)^T = (1.83, 0, 0)^T

min (1000:1.83 = 545.55;-;300:1 = 300;) = 300

Итерация № 3.

Матрица C.

C = (0, -1, 0, 0, 1, 1, 0)

Вектор С не содержит отрицательных элементов. Первый этап симплекс-метода завершен.

Второй этап. Удаляем столбцы с искусственными переменными. Заменим вектор оценок С на целевую функцию.

Выразим базисные переменные:

x₁ = 600-x₄-2x₅

x₂ = 300-x₅

которые подставим в целевую функцию:

F (X) = 8100+x₄+27x₅

Имеем:

Матрица коэффициентов A = a_ij

Матрица b.

Итерация № 1.

Базисные переменные: = (3, 1, 2)

Матрица C:

C = (0, 0, 0, -1, -27)

C_{B (3,1,2)} = (0, 0, 0)

C_{N (4,5)} = (-1, -27, 0, 0)

Матрица N формируется из матрицы, А из соответствующих столбцов с номерами N.

Вычисляем:

u = c_BB^-1 = (0, 0, 0)

Умножаем вектор u на матрицу N: uN = (0, 0, 0, 0)

C^* = C_N — uN = (-1, -27, 0, 0)

Откуда номер направляющего столбца s = 2 (индекс максимального по модулю значения из отрицательных элементов).

a^* = B^-1 (a₁₂,…, a_m2)^T = (1.83, 0, 0)^T

min (450.1:1.83 = 245.55;-;-;) = 245.55

Откуда номер направляющей строки r = 1 (индекс минимального значения).

Итерация № 2.

Матрица C:

C = (0, 0, 0, -1, -27)

Вектор С не содержит отрицательных элементов. Найдено оптимальное решение X.

Вектор результатов X = (1091.11, 545.55)^T

Значение целевой функции F (X) = b x c = 14 729.95

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

Оптимальный план можно записать так:

x₁ = 1091.11

x₂ = 545.55

F (X) = 1*1091.11 + 25*545.55 = 14 729.95

Выполним проверку решения в среде MS Excel. Введем таблицу исходных данных задачи, с помощью надстройки «Поиск решения» установим все требуемые ограничения и выполним данную задачу (рисунок 4.1 — 4.2).

Рисунок 4.1 — Окно «Поиск решения»

Рисунок 4.2 — Результаты выполнения проверки Как видно результаты, найденные в среде MS Excel, совпадают с результатами, полученными ранее, что свидетельствует об их правильности.

4.2 Описание проекта

Схема проекта отражает иерархию окон приложения. Схема представлена на рисунке 4.3.

Рисунок 4.3 — Схема приложения

Схема классов проекта представлена на рисунке 4.4. Реализация табличного симплекс-метода содержится в классе ClassTablSimpl. Класс ClassModifSimpl служит для реализации модифицированного симплекс-метода. Класс MarkaKlass отвечает за выбор метода решения задачи.

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

При выборе «Математическая модель» открывается окно просмотра задачи курсового проекта и математической модели (рисунок 4.6).

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

Рисунок 4.4 — Схема классов Рисунок 4.5 — Окно главного меню приложения Рисунок 4.6 — Окно «Математическая модель»

Рисунок 4.7 — Окно «Симплекс»

Выбрав пункт меню «Экспорт в Word» в окне «Симплекс» можно экспортировать поитерационное решение, для этого необходимо выбрать нужный пункт меню (рисунок 4.8). И в появившемся окне указать путь и имя файла для экспорта (рисунок 4.9). Решение отобразиться в файле MS Word. (рисунок 4.10).

Рисунок 4.8 — Меню программы окна «Симплекс»

Рисунок 4.9 — Экспорт файла

Рисунок 4.10 — Поитерационное решение симплекс-методом.

Экспорт в Excel служит для создания шаблона решения нашей задачи в MS Excel (рисунок 4.11). Так же тут находится пункт меню «Справка», которым можно открыть контекстную справку, которая поможет в работе с приложением (рисунок 4.12).

Рисунок 4.11 — Шаблон для решения задачи в MS Excel

Рисунок 4.12 — Справка

При выборе «Симплекс модифицированный» открывается окно для решения задачи модифицированным симплекс-методом. Форма окна аналогична форме «Симплекс». Форма содержит компоненты содержащие таблицы-данные необходимые для решения задачи, и поле просмотра поитерационного решения. (рисунок 4.13). Поитерационное решение представлено на рисунке 4.14−4.15.

Рисунок 4.13 — Окно «Модифицированный симплекс»

Рисунок 4.14 — Поитерационное решение

Рисунок 4.15 — Поитерационное решение

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

5. Испытание модели на чувствительность

реклама время оптимизационный симплекс

Испытание модели на чувствительность будет произведено при помощи сервиса Excel «Поиск решения».

Анализ чувствительности состоит из следующих этапов:

1. Выбор ключевого показателя, то есть такого параметра, относительно которого и рассчитывается чувствительность проекта.

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

2. Выбор факторов, которые влияют на эти показатели.

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

3. Расчет значений ключевых показателей на разных этапах реализации проекта.

На рисунке 5.1−5.2 показан лист отчета по результатам MS Excel, из которого видно, что бюджет и пропорциональное ограничение по времени на рекламу прямо пропорционально влияют на экономическую выгоду и полностью используются.

Рисунок 5.1 — Отчёт по результатам Рисунок 5.2 — Результаты поиска решения Если изменить количество времени на радио и телевизионную рекламу на 2000 и 500 соответственно. И получаем уменьшение эффективности рекламы. На рисунке 5.3 отображено, что решение является единственным верным и без потери эффективности изменить ключевые параметры нельзя.

Рисунок 5.3 — Результаты поиска решения Учитывая то, что эффективность рекламы напрямую зависит от бюджета, при увеличении бюджета до 1100 условных единиц. Экономический эффект возрастет.

Рисунок 5.4 — Результаты поиска решения

Заключение

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

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

Результатами решения задачи стали:

— оптимальное распределение времени на различные типы рекламы ;

— максимальная удельная прибыль от рекламы;

В процессе работы сделаны следующие выводы:

— полученное решение является единственно оптимальным;

— увеличение бюджета прямо пропорционально влияет на эффективность продаж.

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

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

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

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

1. Галеев Э. М. Оптимизация: теория, примеры, задачи / Э. М. Галеев, В. М. Тихомиров. — М.: Элиторнал УРСС, 2000. — 320 с.

2. Орлов А. И. Устойчивость в социально-экономических моделях. М.: Наука, 1986. — 294 с.

3. Поляк Б. Т.

Введение

в оптимизацию — М.: Наука. Главная редакция физико-математической литературы, 1983. — 384 с.

4. Семушин И. В. Практикум по методам оптимизации: Учеб. пособие для вузов. — Ульяновск: УлГТУ, 1999. — 148с.

5. Смородинский С. С. Оптимизация решений на основе методов и моделей мат. программирования: Учеб. Пособие по курсу «Системный анализ и исследование операций» для студ. спец. «Автоматизированные системы обработки информации» дневной и дистанционной форм обучения / С. С. Смородинский, Н. В. Батин. — Мн.: БГУИР, 2003. — 136 с.: ил.

Приложение

Листинг класса, реализующего табличный симплекс-метод

package MarkaKlass;

import javax.swing.JTextArea;

public class ClassTablSimpl {

public int nRow, nCol; // Количество строк и столбцов

public double kanonMatrix[][];

public int kanonNazvVert[], kanonNazvGor[];

public double ishMatrix[][];

public double vertX[], horzX[], beta[], Fmat[];

public int vertZn[]; public int SPx[], BPx[]; public double XBaz[]; //массив базисных решений

public int colXBaz; public double elem; public int elemi, elemj, bolsrav;

public int kolmin = 1; public int minmax; //если 0 то min, если max то 1

public JTextArea Text; public int chek; public String WriteForWordS = «» ;

ClassTablSimpl () { nRow = 0; nCol = 0; } ;

// Функция задания начальных данных

public void SetSize (int row, int col, int mnmx, JTextArea text) {

nRow = row; nCol = col; colXBaz = col + row; horzX = new double[col];

XBaz = new double[colXBaz]; Fmat = new double[col + 1]; vertX = new double[row];

beta = new double[row]; vertZn = new int[row]; SPx = new int[col];

BPx = new int[row]; ishMatrix = new double[nRow][nCol]; kanonMatrix = new double[nRow][nCol];

minmax = mnmx; Text = text;

for (int i = 0; i < colXBaz; i++) { XBaz[i] = 0; }

};

// Функция округления чисел

public double roundDownScale (double aValue, int num) {

double zn;

zn = Math. pow (10, num);

if (aValue > 0) { return (int) (aValue * zn + 0.5) / zn;

} else { return (int) (aValue * zn) / zn; } }

//Функция для вывода определенного количества символов

public String addSpaces (String s, int n) {

int kol_vo;

if (s.length () < n) { kol_vo = n — s. length ();

} else { return s; }

int right = kol_vo / 2; int left = kol_vo — right;

for (int i = 1; i <= left; i++) { s = «» + s; }

for (int j = 1; j <= right; j++) { s = s + ««; }

return s; }

//Формирование исходной симплекс-таблицы

public void FISimplTabl () {

for (int i = 0; i < nRow; i++) { for (int j = 0; j < nCol; j++) {

kanonMatrix[i][j] = ishMatrix[i][j]; beta[i] = vertX[i]; SPx[j] = j + 1; BPx[i] = nCol + 1 + i;

} }

for (int j = 0; j < nCol; j++) { Fmat[j] = horzX[j] * (-1); }

Fmat[nCol] = 0; //если стоит знак >=

for (int i = 0; i < nRow; i++) {

for (int j = 0; j < nCol; j++) { if (vertZn[i] == 0) { kanonMatrix[i][j] = kanonMatrix[i][j] * (-1);

} } }

for (int i = 0; i < nRow; i++) { if (vertZn[i] == 0) { beta[i] = beta[i] * (-1); }}}

//определение базисного решения

public void BasResh () {

WriteForWordS = «»; for (int i = 0; i < colXBaz; i++) { XBaz[i] = 0; }

for (int i = 0; i < nRow; i++) { XBaz[BPx[i] - 1] = beta[i]; }

Text.append («Определение базисного решения: nX = {n»);

WriteForWordS += «Определение базисного решения: rX = {r» ;

if (chek == 1) { for (int i = 0; i < colXBaz; i++) {

Text.append («tx» + (i + 1) + «= „+ (int) roundDownScale (XBaz[i], 0) + “ ;n»);

WriteForWordS += «tx» + (i + 1) + «= „+ (int) roundDownScale (XBaz[i], 0) + “ ;r» ;

}} else { for (int i = 0; i < colXBaz; i++) {

Text.append («tx» + (i + 1) + «= „+ roundDownScale (XBaz[i], 2) + “ ;n»);

WriteForWordS += «tx» + (i + 1) + «= „+ roundDownScale (XBaz[i], 2) + “ ;r» ;

} }

Text.append («}.n»);

WriteForWordS += «}.r»; }

//определение базисного решения

public void FinishResh () {

WriteForWordS = «»; WriteForWordS += «r» ;

Text.append («n»); for (int i = 0; i < colXBaz; i++) { XBaz[i] = 0; }

for (int i = 0; i < nRow; i++) { XBaz[BPx[i] - 1] = beta[i]; }

if (chek == 1) { for (int i = 0; i < nCol; i++) {

Text.append («Значение х» + (i + 1) + «= «+ (int) roundDownScale (XBaz[i], 0) + «n»);

WriteForWordS += «Значение х» + (i + 1) + «= «+ (int) roundDownScale (XBaz[i], 0) + «r»; }

Text.append («Значение F (x) = «+ (int) roundDownScale (Fmat[nCol], 0) + ««);

WriteForWordS += «Значение F (x) = «+ (int) roundDownScale (Fmat[nCol], 0) + ««;

} else { for (int i = 0; i < nCol; i++) {

Text.append («Значение х» + (i + 1) + «= «+ roundDownScale (XBaz[i], 2) + «n»);

WriteForWordS += «Значение х» + (i + 1) + «= «+ roundDownScale (XBaz[i], 2) + «r»; }

Text.append («Значение F (x) = «+ roundDownScale (Fmat[nCol], 2) + ««);

WriteForWordS += «Значение F (x) = «+ roundDownScale (Fmat[nCol], 2) + ««;

}}

//определение совместна ли система

public int Sovm () {

int pr = 0; int proverka[] = new int[nRow];

for (int i = 0; i < nRow; i++) { pr = 0; if (beta[i] < 0) { pr = 1;

for (int j = 0; j < nCol; j++) { if (kanonMatrix[i][j] < 0) { pr = pr + 1; } } }

proverka[i] = pr;}

int flag = 0; for (int i = 0; i < nRow; i++) { if (proverka[i] == 1) { flag = 1;}}

if (kolmin == 0) { flag = 0; }

return flag;

}

//определение ограниченности целевой функции

public int Ogranic () {

int pr = 0; int proverka[] = new int[nCol];

for (int j = 0; j < nCol; j++) { pr = 0;

if (Fmat[j] < 0) { pr = 1;

for (int i = 0; i < nRow; i++) { if (kanonMatrix[i][j] > 0) { pr = pr + 1; } } }

proverka[j] = pr;}

int flag = 0;

for (int j = 0; j < nCol; j++) {if (proverka[j] == 1) { flag = 1; } }

return flag; }

//проверка допустимого базисного решения

public int DopBazResh () {

int flag = 0;

for (int i = 0; i < nCol; i++) { if (XBaz[i] < 0) { flag = 1; }} return flag; }

//проверка на оптимальность

public int Optimal () { int flag = 0; for (int j = 0; j < nCol; j++) { if (Fmat[j] < 0) { flag = 1; //проверка для min

} }

int flag1 = 0; for (int i = 0; i < nRow; i++) {if (beta[i] < 0) {flag1 = flag1 + 1; } }

if (flag1 > 0) {flag = 1;}

return flag;}

//поиск разрешающего элемента

public void PoiskRazrElem () {

double mini = 0, minj = 0;

int nom_mini = 0, nom_minj = 0;

elem = 0; elemi = 0; elemj = 0; int flag1 = 0;

for (int i = 0; i < nRow; i++) { if (beta[i] < 0) { flag1 = flag1 + 1;} }

if (flag1 > 0) {for (int i = 0; i < nRow; i++) { if (beta[i] < mini) {

mini = beta[i]; nom_mini = i; } }

kolmin = 0; for (int j = 0; j < nCol; j++) {

if (kanonMatrix[nom_mini][j] < 0) { kolmin = kolmin + 1;}}

for (int j = 0; j < nCol; j++) { if (kanonMatrix[nom_mini][j] < minj) { nom_minj = j; } }

} else { //ищем минимальный элемент в строке

for (int j = 0; j < nCol; j++) { if (Fmat[j] < minj) //————-++++++

{ minj = Fmat[j]; nom_minj = j; } }

double betatmp[] = new double[nRow];

for (int i = 0; i < nRow; i++) { betatmp[i] = 0; }

for (int i = 0; i < nRow; i++) { if ((kanonMatrix[i][nom_minj] >= 0) && (kanonMatrix[i][nom_minj] ≠ 0)) {

betatmp[i] = beta[i] / kanonMatrix[i][nom_minj]; } else {betatmp[i] = -1; } }

for (int i = 0; i < nRow; i++) { if (betatmp[i] >= 0) { nom_mini = i; break;}}

mini = betatmp[nom_mini];

for (int i = 0; i < nRow; i++) { if ((betatmp[i] >= 0) && (betatmp[i] < mini)){

mini = betatmp[i]; nom_mini = i; } }}

elem = kanonMatrix[nom_mini][nom_minj];

elemi = nom_mini;

if (kolmin == 0) { elemj = -1; } else { elemj = nom_minj; } }

public void PreobrTabl () {

double kanonMatrix1[][] = new double[nRow][nCol];

double Fmat1[] = new double[nCol + 1];

double beta1[] = new double[nRow];

PoiskRazrElem ();

if (elemj >= 0) { int prom = SPx[elemj];

SPx[elemj] = BPx[elemi]; BPx[elemi] = prom;

System.arraycopy (beta, 0, beta1, 0, nRow);

System.arraycopy (Fmat, 0, Fmat1, 0, nCol + 1);

for (int i = 0; i < nRow; i++) {System.arraycopy (kanonMatrix[i], 0, kanonMatrix1[i], 0, nCol); }

for (int i = 0; i < nRow; i++) { if (i == elemi) { beta[i] = beta1[i] / elem; } else { beta[i] = beta1[i] - ((kanonMatrix1[i][elemj] * beta1[elemi]) / elem);} }

for (int j = 0; j < nCol; j++) { if (j == elemj) { Fmat[j] = (-1) * (Fmat1[j] / elem);

} else { Fmat[j] = Fmat1[j] - ((kanonMatrix1[elemi][j] * Fmat1[elemj]) / elem); } }

Fmat[nCol] = Fmat1[nCol] - ((beta1[elemi] * Fmat1[elemj]) / elem);

for (int i = 0; i < nRow; i++) { for (int j = 0; j < nCol; j++) {

if ((i == elemi) && (j == elemj)) { kanonMatrix[i][j] = 1. / kanonMatrix1[i][j];

} else if ((j == elemj) && (i ≠ elemi)) { kanonMatrix[i][j] = (-1) * (kanonMatrix1[i][j] / elem);

} else if ((i == elemi) && (j ≠ elemj)) { kanonMatrix[i][j] = kanonMatrix1[i][j] / elem;

} else { kanonMatrix[i][j] = kanonMatrix1[i][j] - ((kanonMatrix1[elemi][j] * kanonMatrix1[i][elemj]) / elem); } } }

Text.append («n»); Print ();Text.append («n»);} }

public void Print () «); WriteForWordS += «

public void Opr () {

WriteForWordS = «»; int mnogitel = 0;

if ((minmax == 0)) { mnogitel = -1; Fmat[nCol] = mnogitel * Fmat[nCol]; }}}

Листинг класса реализующего модифицированный симплекс-метод

package kursovai;

import javax.swing.JTextArea;

public class ClassModifSimpl {

public int nRow, nCol; // Количество строк и столбцов

public double ishMatrix[][];

public double peremenXB[][];

public double vertX[], horzX[], beta[], Fmat[];

public int vertZn[];

public double Matrixkoefic[][];

public int SPx[], BPx[];

public JTextArea Text; public int nColReal;

//элементы для модифицированного метода

public double G[][]; //элементы расширенной матрицы без единичной

public double Bed[][]; //единичная матрица

public double bprav[]; //правая часть ограничений

public double piT[]; //симплекс множители

public double cT[], cT1[]; //коэффициенты целевой функции

public double cTst[]; //коэффициенты целевой функции

public int el, es, k; //промежуточные результаты

public double aks, cs;

public int NB[]; //номера базисных переменных

public int NF[]; //номера свободных переменных

public double z; //значение целевой функции

public double BR[]; //решение

public double ashs[][]; //решение

public double as[][];

public int proverstroka = 0;

public int proverstolbec = 0;

public double XBaz[]; //массив базисных решений

public int chek;

public int iteration;

public int mnmx1;

public String WriteForWordS = «» ;

ClassModifSimpl () { nRow = 0; nCol = 0; } ;

// Функция задания начальных данных

public void SetSize (int row, int col, int mnmx, JTextArea text) {

nRow = row; nCol = col;ishMatrix = new double[nRow][nCol];

horzX = new double[col]; vertX = new double[row]; vertZn = new int[row];

beta = new double[row]; BPx = new int[row];

Text = text; G = new double[nRow][nCol]; piT = new double[nRow];

bprav = new double[nRow]; cT = new double[nCol]; cT1 = new double[nCol];

cTst = new double[nCol]; ashs = new double[nCol][1]; NB = new int[nRow];

NF = new int[nCol]; Bed = new double[nRow][nRow];

mnmx1 = mnmx; for (int i = 0; i < nRow; i++) { for (int j = 0; j < nRow; j++) { if (i == j) {

Bed[i][j] = 1; } else { Bed[i][j] = 0; } } } } ;

//запишем в канонической форме

public void CanonForma () {

int kol = 0; nColReal = nCol; for (int i = 0; i < nRow; i++) { kol = kol + 1; }

peremenXB = new double[kol][kol];

for (int i = 0; i < kol; i++) { for (int j = 0; j < kol; j++) { if (i == j) { peremenXB[i][j] = 1; } else {

peremenXB[i][j] = 0; } } }

nColReal = nColReal + kol; Matrixkoefic = new double[nRow][nColReal];

SPx = new int[nColReal]; Fmat = new double[nColReal + 1];

for (int i = 0; i < nRow; i++) { if (vertZn[i] == 1) { for (int j = 0; j < nCol; j++) { Matrixkoefic[i][j] = ishMatrix[i][j]; }beta[i] = vertX[i]; }

if (vertZn[i] == 2) { for (int j = 0; j < nCol; j++) { Matrixkoefic[i][j] = ishMatrix[i][j]; }

beta[i] = vertX[i]; }

if (vertZn[i] == 3) { for (int j = 0; j < nCol; j++) { Matrixkoefic[i][j] = (-1) * ishMatrix[i][j]; }

beta[i] = (-1) * vertX[i]; }}

for (int i = 0; i < nRow; i++) { for (int j = nCol; j < nColReal; j++) {

Matrixkoefic[i][j] = peremenXB[i][j — nCol]; } }

for (int j = 0; j < nColReal; j++) { SPx[j] = j + 1; }

for (int i = 0; i < nRow; i++) { BPx[i] = nCol + 1 + i; }

for (int j = 0; j < nCol; j++) { Fmat[j] = horzX[j] * (-1); }

for (int j = nCol; j < nColReal + 1; j++) { Fmat[j] = 0; }

as = new double[nRow][nColReal];; for (int i = 0; i < nRow; i++) {

for (int j = 0; j < nColReal; j++) { as[i][j] = Matrixkoefic[i][j]; } } }

public void FormirElMod () {

BR = new double[nColReal]; for (int i = 0; i < nRow; i++) { piT[i] = 0; }

for (int i = 0; i < nRow; i++) { for (int j = 0; j < nCol; j++) { G[i][j] = Matrixkoefic[i][j]; } }

for (int j = 0; j < nCol; j++) { cT[j] = horzX[j]; NF[j] = j; }

for (int j = 0; j < nCol; j++) { cTst[j] = horzX[j]; }

for (int j = 0; j < nCol; j++) { cT1[j] = horzX[j]; }

for (int j = nCol; j < nColReal; j++) { NB[j — nCol] = j; }

z = 0;for (int j = 0; j < nColReal; j++) { if (j < nCol) { BR[j] = 0; } else { BR[j] = beta[j — nCol]; } }

for (int i = 0; i < nRow; i++) { bprav[i] = beta[i]; } }

public double[][] myCoolMethod (double[][] M1, double[][] M2, int ar, int cr, int br) {

double[][] R = new double[ar][cr];

for (int i = 0; i < ar; i++) { for (int j = 0; j < cr; j++) { for (int k = 0; k < br; k++) { R[i][j] = R[i][j] + M1[i][k] * M2[k][j]; } } } return R; }

public void ishznmodmet () {

Text.append («Обратная матрица: n»);

WriteForWordS += «Обратная матрица: r» ;

for (int i = 0; i < nRow; i++) { Text. append («|»); for (int j = 0; j < nRow; j++) {

Text.append («» + addSpaces (String.valueOf (roundDownScale (Bed[i][j], 1)), 4) + ««);

} Text. append («|n»); }

for (int i = 0; i < nRow; i++) { WriteForWordS += «|»; for (int j = 0; j < nRow; j++) {

WriteForWordS += «» + addSpaces (String.valueOf (roundDownScale (Bed[i][j], 1)), 4) + ««; }

WriteForWordS += «|r»; }}

public void ProvVectorKriterOpt () {

//умножение 2-ух матриц

int ar = 1, br = nRow, cr = nCol; double[][] M1 = new double[ar][br];

double[][] M2 = new double[br][cr]; double[][] R1 = new double[ar][cr];

for (int i = 0; i < ar; i++) { for (int j = 0; j < br; j++) { M1[i][j] = piT[j]; } }

for (int i = 0; i < br; i++) {

for (int j = 0; j < cr; j++) {

M2[i][j] = G[i][j];

}

}

R1 = myCoolMethod (M1, M2, ar, cr, br);

for (int i = 0; i < ar; i++) {

for (int j = 0; j < cr; j++) {

cT[j] = cTst[j] + R1[i][j];

}

}

//составим строку (cT, piT) если нет отрицательных элементов то решения найдено

double[] picT = new double[nRow + nCol];

for (int i = 0; i < nRow + nCol; i++) {

if (i < nCol) {

picT[i] = cT[i];

} else {

picT[i] = piT[i — nCol];

}

}

int kolvootr = 0;

for (int i = 0; i < nCol; i++) {

if (picT[NF[i]] < 0) {

kolvootr = kolvootr + 1;

}

}

Text.append («Проверка на оптимальность: кол-во отрицательных элементов вектора критерия оптимальности = «);

WriteForWordS += «Проверка на оптимальность: кол-во отрицательных элементов вектора критерия оптимальности = «;

Text.append (kolvootr + ««);

Text.append («n»);

WriteForWordS += kolvootr + ««;

WriteForWordS += «r» ;

if (kolvootr <= 0) {

proverstroka = 1;

} else {

WriteForWordS += «rЗначения после «+ iteration + «итерации :r» ;

Text.append («nЗначения после «+ iteration + «итерации :n»);

iteration++;

proverstroka = 0;

double min = picT[NF[0]]; int poiskmin = NF[0];

el = -1; es = -1;

for (int i = 0; i < nCol; i++) {

if (picT[NF[i]] < min) { min = picT[NF[i]]; poiskmin = NF[i]; } }

for (int j = 0; j < nCol; j++) { if (NF[j] == poiskmin) { el = j; es = NF[el]; }}

cs = min;

//рассчитываем ashs

//умножение 2-ух матриц

ar = nRow; br = nRow; cr = 1;

M1 = new double[ar][br]; M2 = new double[br][cr];

for (int i = 0; i < ar; i++) { for (int j = 0; j < br; j++) { M1[i][j] = Bed[i][j]; }}

for (int i = 0; i < br; i++) { for (int j = 0; j < cr; j++) { M2[i][j] = as[i][es]; }}

ashs = myCoolMethod (M1, M2, ar, cr, br);

double[] Temp = new double[nRow];

for (int i = 0; i < nRow; i++) { if (ashs[i][0] <= 0) { Temp[i] = 99 999; }else{

Temp[i] = bprav[i] / Math. abs (ashs[i][0]); } }

double minelem = Temp[0];

int k = 0;

for (int i = 0; i < nRow; i++) {

if (Temp[i] < minelem) {

minelem = Temp[i];

k = i;

}

}

aks = ashs[k][0];

//Text.append («aks -> «); Text. append (aks+» «); Text. append («n»);

int tem = 0;

tem = NB[k];

NB[k] = NF[el];

NF[el] = tem;

for (int j = 0; j < nCol; j++) «);

for (int j = 0; j < nCol; j++) «;

bprav[k] = bprav[k] / aks;

for (int i = 0; i < nRow; i++) {

if (i ≠ k) {

bprav[i] = bprav[i] - ashs[i][0] * bprav[k];

}

}

z = z — cs * bprav[k];

for (int j = 0; j < nRow; j++) {

Bed[k][j] = Bed[k][j] / aks;

}

for (int i = 0; i < nRow; i++) {

for (int j = 0; j < nRow; j++) {

if (i ≠ k) {

Bed[i][j] = Bed[i][j] - Bed[k][j] * ashs[i][0];

}

}

}

Text.append («Обратная матрица: n»);

for (int i = 0; i < nRow; i++) {

Text.append («|»);

for (int j = 0; j < nRow; j++) {

Text.append («» + addSpaces (String.valueOf (roundDownScale (Bed[i][j], 1)), 4) + ««);

}

Text.append («|n»);

}

for (int i = 0; i < nRow; i++) {

WriteForWordS += «|» ;

for (int j = 0; j < nRow; j++) {

WriteForWordS += «» + addSpaces (String.valueOf (roundDownScale (Bed[i][j], 1)), 4) + ««;

}

WriteForWordS += «|r» ;

}

Text.append («n»);

WriteForWordS += «r» ;

for (int j = 0; j < nRow; j++) {

piT[j] = piT[j] - cs * Bed[k][j];

}

for (int j = 0; j < nColReal; j++) {

BR[j] = 0;

}

for (int j = 0; j < nRow; j++) {

BR[NB[j]] = bprav[j];

}

BasResh ();

}

}

public void ProvVectorSvobodnChlen () {

int kolotrbet = 0;

for (int i = 0; i < nRow; i++) {

if (bprav[i] < 0) {

kolotrbet = kolotrbet + 1;

}

}

WriteForWordS += «Проверка на оптимальность: кол-во отрицательных элементов вектора свободных членов =»;

Text.append («Проверка на оптимальность: кол-во отрицательных элементов вектора свободных членов =»);

WriteForWordS += kolotrbet + ««;

WriteForWordS += «r» ;

Text.append (kolotrbet + ««);

Text.append («n»);

if (kolotrbet <= 0) {

proverstolbec = 1;

} else {

WriteForWordS += «nЗначения после «+ iteration + «итерации :r» ;

Text.append («nЗначения после «+ iteration + «итерации :n»);

iteration++;

proverstolbec = 0;

double minb = bprav[0];

int k2 = 0;

for (int i = 0; i < nRow; i++) {

if (bprav[i] < minb) {

minb = bprav[i];

k2 = i;

}

}

WriteForWordS += «Из базиса выводим x» ;

WriteForWordS += (NB[k2] + 1) + ««;

WriteForWordS += «r» ;

Text.append («Из базиса выводим x»);

Text.append ((NB[k2] + 1) + ««);

Text.append («n»);

int ar = 1, br = nRow, cr = nCol;

double[][] M1 = new double[ar][br];

double[][] M2 = new double[br][cr];

double[][] akTs = new double[ar][cr];

for (int i = 0; i < ar; i++) {

for (int j = 0; j < br; j++) {

M1[i][j] = Bed[k2][j];

}

}

for (int i = 0; i < br; i++) {

for (int j = 0; j < cr; j++) {

M2[i][j] = G[i][j];

}

}

akTs = myCoolMethod (M1, M2, ar, cr, br);

double[][] akTsp = new double[ar][cr + nRow];

for (int j = 0; j < cr + nRow; j++) {

if (j < cr) {

akTsp[0][j] = akTs[0][j];

} else {

akTsp[0][j] = Bed[k2][j — cr];

}

}

double[] picT = new double[nRow + nCol];

for (int i = 0; i < nRow + nCol; i++) {

if (i < nCol) {

picT[i] = cT[i];

} else {

picT[i] = piT[i — nCol];

}

}

double[] Temp1 = new double[nCol + nRow];

for (int j = 0; j < nCol + nRow; j++)

{

if (akTsp[0][j] >= 0) {

Temp1[j] = 99 999;

} else {

Temp1[j] = picT[j] / Math. abs (akTsp[0][j]);

}

}

double minelem1 = Temp1[NF[0]];

el = -1;

es = -1;

int poiskmin1 = NF[0];

for (int j = 0; j < nCol; j++) {

if (Temp1[NF[j]] < minelem1) {

minelem1 = Temp1[NF[j]];

poiskmin1 = NF[j];

}

}

for (int j = 0; j < nCol; j++) {

if (NF[j] == poiskmin1) {

el = j;

es = NF[el];

}

}

cs = cT[poiskmin1];

//умножение 2-ух матриц

ar = nRow;

br = nRow;

cr = 1;

M1 = new double[ar][br];

M2 = new double[br][cr];

for (int i = 0; i < ar; i++) {

for (int j = 0; j < br; j++) {

M1[i][j] = Bed[i][j];

}

}

for (int i = 0; i < br; i++) {

for (int j = 0; j < cr; j++) {

M2[i][j] = as[i][es];

}

}

ashs = myCoolMethod (M1, M2, ar, cr, br);

aks = ashs[k2][0];

int tem = 0;

tem = NB[k2];

NB[k2] = NF[el];

NF[el] = tem;

for (int j = 0; j < nCol; j++)

Text.append (addSpaces (String.valueOf («x» + (NF[j] + 1)), 8) + «

bprav[k2] = bprav[k2] / aks;

for (int i = 0; i < nRow; i++) {

if (i ≠ k2) {

bprav[i] = bprav[i] - ashs[i][0] * bprav[k2];

}

}

z = z — cs * bprav[k2];

for (int j = 0; j < nRow; j++) {

Bed[k2][j] = Bed[k2][j] / aks;

}

for (int i = 0; i < nRow; i++) {

for (int j = 0; j < nRow; j++) {

if (i ≠ k2) {

Bed[i][j] = Bed[i][j] - Bed[k2][j] * ashs[i][0];

}

}

}

WriteForWordS += «Обратная матрица: r» ;

for (int i = 0; i < nRow; i++) {

WriteForWordS += «|» ;

for (int j = 0; j < nRow; j++) {

WriteForWordS += «» + addSpaces (String.valueOf (roundDownScale (Bed[i][j], 1)), 4) + ««;

}

WriteForWordS += «|r» ;

}

WriteForWordS += «r» ;

Text.append («Обратная матрица: n»);

for (int i = 0; i < nRow; i++) {

Text.append («|»);

for (int j = 0; j < nRow; j++) {

Text.append («» + addSpaces (String.valueOf (roundDownScale (Bed[i][j], 1)), 4) + ««);

}

Text.append («|n»);

}

Text.append («n»);

for (int j = 0; j < nRow; j++) {

piT[j] = piT[j] - cs * Bed[k2][j];

}

ar = 1; br = nRow; cr = nCol;

M1 = new double[ar][br];

M2 = new double[br][cr];

double[][] R1 = new double[ar][cr];

for (int i = 0; i < ar; i++) { for (int j = 0; j < br; j++) { M1[i][j] = piT[j]; } }

for (int i = 0; i < br; i++) { for (int j = 0; j < cr; j++) { M2[i][j] = G[i][j]; } }

R1 = myCoolMethod (M1, M2, ar, cr, br);

for (int i = 0; i < ar; i++) { for (int j = 0; j < cr; j++) { cT[j] = cTst[j] + R1[i][j]; } }

for (int j = 0; j < nColReal; j++) { BR[j] = 0; }

for (int j = 0; j < nRow; j++) { BR[NB[j]] = bprav[j]; } BasResh (); } }