Математическое программирование

СОДЕРЖАНИЕ

 

 

ВВЕДЕНИЕ

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

Модель задачи математического программирования включает:

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

Целевая функция  позволяет выбирать наилучший вариант  из множества возможных.

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

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

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

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

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

Имитационное  моделирование позволяет имитировать поведение системы во времени. Можно имитировать поведение тех объектов, реальные эксперименты с которыми дороги, невозможны или опасны.

Цель имитационного  моделирования состоит в воспроизведении  поведения исследуемой системы  на основе результатов анализа наиболее существенных взаимосвязей между ее элементами.

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

1. решение с помощью программы SimplexWin;
2. решение с построением двойственной задачи, используя программу SimplexWin»;
3. решение симплексным методом;
4. решение симплексным (ручным) методом;
5. решения через «Поиск решения» Excel.

 

 

 

1 ПОСТАНОВКА  ЗАДАЧИ

Пароход может  быть использован для перевозки  груза четырех наименований. Масса  единицы груза j – го вида m_j (в тоннах), стоимость с_j ( в условных денежных единицах), объем (в м⁸) Vj (j=1,4) . на пароход может быть погружено не более М т груза общим объемом, не превышающим V м³. Кроме того, груза k-го вида на пароход можно взять не более d_k единиц. Сколько единиц каждого груза следует поместить на пароход, чтобы общая стоимость перевозимого груза была максимальной? Значения m_j,c_j, V_j, k, m, V, d_k приведены в таблице:

Таблица 1.1

Исходные  данные

j	Mj	cj	Vj
1	4	12	1	V=21
2	1	11	3	M=20
3	2	4	2	k=1
4	1	5	3	dk=10

 

 

 

2 СОСТАВЛЕНИЕ  МАТЕМАТИЧЕСКОЙ МОДЕЛИ

Для решения  данной задачи указанными методами решений  составим математическую модель.

Пусть Х₁ – груз 1 типа, Х₂ – груз 2 типа, Х₃ – груз 3 типа, Х₄ – груз 4 типа. Целевая функция имеет следующий вид:

Z(x) = 12*x₁+11* x₂ + 4* x₃  + 5* x₄ →max

4*x₁+1* x₂  +2* x₃ + 1*х₄≤ 20 –для общей массы груза, 1*x₁+3* x₂ +2* x₃ + 3*х₄≤ 21 – для общего объема груза, где d_k≤10 или x_k≤10.

x₁≥0, x₂≥0, x₃≥0, x₄≥0 – условие не отрицательности переменных. Получим математическую модель задачи:

Z(x) = 12*x₁+11* x₂ + 4* x₃  + 5* x₄ →max

 

_{3 МЕТОДЫ РЕШЕНИЯ  ЗАДАЧ}

_{3.1 Решение с помощью  программы  Simplex Win}

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

Рис. 3.1.1 Диалоговое окно программы Simplex Win

Открываем пункт  меню «Настройки», выбираем пункт «Размер  матрицы». (См. рис. 3.1.2)

Рис. 3.1.2 Настройка  размера матрицы

В данном случае количество уравнений – 2, количество переменных – 4, нажимаем «ОК». Затем вносим соответствующие данные, в поле «Введите элементы матрицы» ограничений, в поле «Введите элементы функции» коэффициенты нулевой функции. (См. рис. 3.1.3)

Рис. 3.1.3 Ввод данных

После ввода  необходимых данных нажимаем кнопку «Вычислить». Программа выполняет  необходимые действия, происходит добавление 2 дополнительных переменных –Х₅, Х₆. (См. рис. 3.1.4)

Рис. 3.1.4 Таблица  результатов

Нажимаем кнопку «Результат», программа производит вычисления и выводит на экран оптимальный план решения задачи. (См. рис. 3.1.5)

Рис. 3.1.5 Полученный результат

По результатам  программы получили:

Х₁ = 3,54 – груз 1-го вида;

Х₂ = 5,81 – груз 2-го вида;

Х₃ = 0 – груз 3-го вида;

Х₄ = 0 – груз 4-го вида.

Z(X) = 106,54 – максимальная стоимость перевозимого груза.

 

3.2 Решение  двойственной задачи линейного  программирования (с помощью программы SimplexWin)

Для решения  этой задачи, с помощью программы SimplexWin необходимо внести  данные в программу (Рис. 3.2.1).

Рис.3.2.1 Внесенные  данные

После выполнения этих действий, выбираем пункт меню «Задача» → «Составление двойственной» (Рис. 3.2.2).

Рис. 3.2.2 Составление  двойственной

После того, как  выбрали «Составить двойственную», программа выдает окно «Ввод ограничений», нажимаем «Ок» (Рис. 3.2.3).

Рис. 3.2.3 Ввод ограничений

Данные ограничения  нас устраивают, следовательно нажимаем «Ок», программа автоматически составляет двойственную модель (Рис. 3.2.4).

Рис. 3.2.4 Двойственная модель задачи

Далее, нажимаем кнопку «Вычислить», получаем таблицу  с результатами вычислений (Рис.3.2.5).

Рис. 3.2.5 Таблица  результатов

Затем нажимаем кнопку «Результат», после чего на экране появляется окно с результатом (Рис. 3.2.6).

Рис 3.2.6 Окно с  результатом

Из полученного  результата видно, что максимальная прибыль составляет 106,54 ден. ед., при транспортировке 2,27  тонны 1-го вида груза, 0 тонн 2-го вида груза, 2,90 тонны 3 –го вида груза и 0  тонн 4-го вида груза.

 

3.3 Симплексный метод решения задачи с помощью программы Excel

Чтобы решить задачу симплексным методом, необходимо сначала  привести ее к каноническому виду. Для этого вводим дополнительные неотрицательные переменные – Х₅, Х₆. Математическая модель задачи принимает вид:

Z(x) = 12*x₁+11* x₂ + 4* x₃  + 5* x₄ + 0*х₅+0*х₆→max

4*х₁+1*х₂+2*х₃+1*х₄+х₅=20;

1*х₁+3*х₂+2*х₃+3*х₄+х₆=21;

 Х₁, Х₂, Х₃, Х₄, Х₅, Х₆ ≥ 0;

Х₁, Х₂, Х₃, Х₄, Х₅, Х₆ – целочисленные.

Строим начальную  опорную таблицу (Рис. 3.3.1).

Рис. 3.3.1 Опорная  таблица

Далее находим  начальное опорное решение, для  этого находим Δ_j, по формуле:

Δ_j=

Найдя коэффициенты Δ_j заполняем первую таблицу симплексного решения (Рис. 3.3.2).

Рис. 3.3.2 Первая таблица симплексного решения

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

Рис. 3.3.3 Оптимальный  план

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

 

3.4 Симплексный   метод решения задачи с помощью Excel

Excel ручным способом

Чтобы решить задачу симплексным методом, необходимо сначала привести ее к каноническому виду. Для этого вводим дополнительные неотрицательные переменные – Х₅, Х₆. Математическая модель задачи принимает вид:

Z(x) = 12*x₁+11* x₂ + 4* x₃  + 5* x₄ + 0*х₅+0*х₆→max

4*х₁+1*х₂+2*х₃+1*х₄+х₅=20;

1*х₁+3*х₂+2*х₃+3*х₄+х₆=21;

 Х₁, Х₂, Х₃, Х₄, Х₅, Х₆ ≥ 0;

Х₁, Х₂, Х₃, Х₄, Х₅, Х₆ – целочисленные.

Строим начальную  опорную таблицу (Рис. 3.4.1).

Рис. 3.4.1 Опорная  таблица

Далее находим  начальное опорное решение. Для  этого находим Δ_j, по формуле:

Δ_j=

Найдя коэффициенты Δ_j заполняем первую таблицу симплексного решения (Рис. 3.4.2).

Рис. 3.4.2 Первая таблица симплексного решения

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

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

Рис. 3.4.3 Вторая таблица симплексного решения

Из данной таблицы видим, что план решения далек от оптимального. Выбираем разрешающий столбец, это Х₂ и разрешающую строку, это строка Х₆ . На их пересечении находится разрешающий элемент. Выводя из базиса  Х₆ и вводя Х₂ получаем следующую таблицу решений (Рис. 3.4.4).

 

Рис. 3.4.4 Третья таблица симплексного решения

 

По результатам  вычислений видно, что найденное решение оптимально, все значения Δ_j отрицательные, значение целевой функции равно 106,54. Отсюда следует, что при перевозке 3,54 тонны груза 1-го вида и 5,81 тонны груза 2 – го вида общая стоимость груза будет составлять 106,54 денежных единиц.

 

ЗАКЛЮЧЕНИЕ

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

При выполнении курсовой работы была решена задача линейного  программирования о выполнении перевозки грузов четырех наименований. Данная задача была 4 различными методами, такими как: