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

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

Введение 3
1 Постановка задачи 5
1.1 Экономическая сущность задачи 5
1.2 Математическая модель 7
1.3 Входные данные 8
1.4 Выходные данные 8
1.5 Организация диалога 9
1.6 Функциональные тесты 11
2 Выбранный метод решения задачи 16
3 Структурное проектирование задачи 20
4 Тестирование 22
5 Анализ качества и надежности 25
6 Анализ результатов решения задачи 26
Заключение 27
Список литературы 29
Приложения

Линейное программирование – математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем выпуклого программирования, которое, в свою очередь, является частным случаем математического программирования. Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джоржем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.
Работа содержит наиболее распространённый метод решения задачи линейного программирования – симплекс-методу. Симплекс-метод является классическим и наиболее прора ботанным методом в линейном программировании.
Актуальность данной темы заключается в том, что в процессе производственной деятельности все предприятия сталкиваются с проблемой нехватки сырья, а также с тем, что выпускаемая продукция должна быть адекватна с экономической точки зрения, другими словами, чтобы её можно было выгодно продать, и чтобы она соответствовала запросам покупателя.
Учитывая всевозрастающую ограниченность ресурсов, очень важно добиваться их максимально эффективного использования. План должен быть разработан настолько умело, чтобы использование ограниченных ресурсов было оптимальным.
Задача оптимизации структуры сырья при планировании выпуска продукции для получения максимальной прибыли является задачей линейного программирования.
Если система имеет хотя бы одно решение, она называется совместной. Несовместные системы не имеют ни одного решения.
Допустимым решением называется совокупность значений переменных, удовлетворяющая системе ограничений и условиям не отрицательности.
Широко используемым на практике методом решения задач линейного программирования является симплексный. Этот метод решения задачи линейного программирования основан на переходе от одного опорного решения к другому, при котором значение целевой функции улучшается (на максимум – увеличивается, на минимум – уменьшается или остаётся на прежнем уровне), при условии, что данная задача имеет оптимальный план.
Целью курсового проекта является разработка программного продукта для решения задач линейного программирования с помощью симплекс-метода.
Основные задачи курсового проекта:
‒ изучить области автоматизации;
‒ разработка математической модели поставленной задачи и её обоснование;
‒ определение практической составляющей задачи, её экономической сущности;
‒ разработка программного продукта.
‒ тест
Для реализации выбран язык программирования Pascal, в качестве среды разработки – пакет CodeGear RAD Studio 2009.

3320
4
10
–9
8
4360
4
6
–2
3
1630
4
–6
5
480
1
380
1
120
1
170
1
1440
–9
–5
12
–7
Найдено максимальное (по абсолютной величине) отрицательное значение в строке – столбец выбран разрешающим.
Найдено положительное значение в строке – строка выбрана разрешающей по правилу: .
Необходимо выполнить симплекс-преобразование.
1400
–4
10
–9
8
2440
–4
6
–2
3
1630
4
–6
5
480
1
380
1
120
1
170
1
5760
9
–5
12
–7
Найдено максимальное (по абсолютной величине) отрицательное значение в строке – столбец выбран разрешающим.
Найдено положительное значение в строке – строка выбрана разрешающей по правилу: .
Необходимо выполнить симплекс-преобразование.
40
–4
10
–9
–8
1930
–4
6
–2
–3
780
4
–6
–5
480
1
380
1
120
1
170
1
6950
9
–5
12
7
Найдено максимальное (по абсолютной величине) отрицательное значение в строке – столбец выбран разрешающим.
Найдено положительное значение в строке – строка выбрана разрешающей по правилу: .
Необходимо выполнить симплекс-преобразование.
4
–0,4
0,1
–0,9
–0,8
1906
–1,6
–190,6
3,4
1,8
764
1,6
–0,4
–2,4
–1,8
480
1
–0,1
376
0,4
–0,1
0,9
0,8
120
1
170
1
6970
7
0,5
7,5
3
Все (значения в столбце ) и (значения в строке ), следовательно, найдено оптимальное решение.
Функция достигает экстремума в точках: Х(, , , )
2 Выбранный метод решения задачи
Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования является симплекс-метод. Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач линейного программирования, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения.
Задача линейного программирования заключается в отыскании вектора , максимизирующего линейную целевую функцию
(1)
при следующих линейных ограничениях
(2)
(3)
Запись задачи линейного программирования в виде (1) – (3) называется нормальной формой задачи. Эту же задачу линейного программирования можно представить в векторно-матричной записи:
(4)
где – вектор коэффициентов целевой функции,
– вектор решения,
– вектор свободных членов,
, , – матрица коэффициентов.
Область называется областью допустимых значений (ОДЗ) задач линейного программирования. Соотношения (2), (3) называются системами ограничений задачи линейного программирования. Так как , то можно ограничиться изучением задачи одного типа.
Решением задачи линейного программирования, или оптимальным планом, называется вектор, удовлетворяющий системе ограничений задачи и оптимизирующий целевую функцию.
Другая форма представления задачи линейного программирования – каноническая. Она имеет вид:

В канонической форме записи задач линейного программирования все свободные переменные, входящие в систему ограничений, должны быть неотрицательными, а все ограничения должны быть представлены равенствами. В этом случае начальное решение является допустимым.
Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности.
Симплекс-метод является наиболее распространённым вычислительным методом, который может быть применён для решения любых задач линейного программирования как вручную, так и с помощью ЭВМ.
Этот метод позволяет переходить от одного допустимого решения к другому, причём так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритм симплекс-метода позволяет также установить, является ли задача разрешимой.
Рассмотрим задачу линейного программирования в канонической форме. Будем искать решение задачи (6), (7), (8).
, (6)
(7)
. (8)
Шаг 1. Положим . Взяв переменные за свободные и положив их равными нулю, а , переобозначив в , – за базисные, находим первую крайнюю точку:
.
Шаг 2. Заполним начальную допустимую симплекс-таблицу
…
…
…
1
…
…
…
…
…