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

Пояснительная записка к курсовой работе по дисциплине

" Технология профессиональной деятельности. Информационный поиск и систематизация знаний"

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

Студента ГИП-111

Осипова Антона Александровича

• Введение
• 1. Блок-схемы основных алгоритмов
• 2. Интерфейсы
• 3. Разработанный код
• 4. Инструкция пользователю по применению программы
• 5. Описание применения программы
• 6. Результаты применения программы
• 7. Ход статистического анализа
• 8. Сопоставление полученных результатов с результатами аналогичных работ
• Выводы
• Литература
• Приложения

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

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

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

План выполнения работы

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

1. Постановка ЗЛП (задачи линейного программирования)

2. Изучен симплекс-метод по интернет ресурсам и учебным пособиям.

3. Решение ЗЛП симплекс-методом на в ручную

4. Разработка алгоритма реализации программной части работы

5. Написание самого кода программы на языке программирования Pascal ABC.

Техническое задание на программу

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

Ключевые слова:

Линейное программирование, симплекс метод, язык программирование, Pascal ABC.

1. Блок-схемы основных алгоритмов

2. Интерфейсы

Интерфейс программа простейший. Он состоит только из диалогового окна.

Рисунок 1

3. Разработанный код

uses crt;

var n, i, l, x3,x4,x5,j, z1, z2,dl1,dl2,dl3,dl4,dl5,k: integer;

i1,j1: integer;

z3,z4,z5,max, m: integer;

a: array [1.20,1.20] of integer;

b: array [1.1000] of real;

g: array [1.20,1.20] of integer;

begin

write ('Введите коэффициенты при целевой функции: ');

readln (z1,z2);

write ('Количество уравнений '); readln (n);

write ('введите x3, x4,x5');

readln (x3,x4,x5);

for i: =1 to n do begin

for j: =1 to 2 do begin

write ('a', i,',', j,'= '); readln (a [i, j]);

end;

write ('b', i,'= '); readln (b [i]);

end;

write ('razmernost, ed mat');

readln (k);

for i1: =1 to k do begin

for j1: =1 to k do begin

if i1=j1 then g [i, j]: =1 else g [i, j]: =0;

write (g [i, j]: 5);

end;

writeln;

end;

begin

writeln ('delta'); // нахождения delta

z3: =0; z4: =0; z5: =0;

dl1: = (a [1,1] *x3+a [2,1] *x4+a [3,1] *x5) — z1;

dl2: = (a [1,2] *x3+a [2,2] *x4+a [3,2] *x5) — z2;

dl3: = (g [1,1] *x3+g [2,1] *x4+g [3,1] *x5) — z3;

dl4: = (a [1,2] *x3+a [2,2] *x4+a [3,2] *x5) — z4;

dl5: = (g [1,3] *x3+a [2,3] *x4+a [3,3] *x5) — z5;

end;

writeln (dl1: 3, dl2: 3, dl3: 3, dl4: 3, dl5: 3);

begin

// макс

if (dl1<0) and (dl2<0) and (dl3<0) and (dl4<0) and (dl5<0)

then

if (dl1>dl2) then max: =abs (dl1)

else max: =abs (dl2);

if (dl3>dl4) then max: =abs (dl3)

else max: =abs (dl4)

end;

writeln (max);

writeln;

end.

4. Инструкция пользователю по применению программы

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

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

.

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

Пусть система ограничений имеет вид

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

которая имеет предпочтительный вид

.

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю .

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

Пусть исходная ЗЛП имеет вид

(1)

(2)

(3)

причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

(4)

(5)

, (6)

Задача (4) — (6) имеет предпочтительный план. Её начальный опорный план имеет вид Если некоторые из уравнений (2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема. Если в оптимальном плане

(7)

М-задачи (4) — (6) все искусственные переменные, то план является оптимальным планом исходной задачи (1) — (3).

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

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

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

Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

Признаки оптимальности.

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

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

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

Ограничения вида «0» — ресурсные ограничения. Справа находится то что мы используем на производстве, слева — то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0» .

Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса — Yi. В систему ограничений они входят с коэффициентом «1». а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin — «+M», при Fmax — «-M»).

Ограничения вида «0» — Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл — перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию — с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.

5. Описание применения программы

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

Рисунок 2. Описание применения программы. Ввод данных

Фрагмент программы которые отвечает за ввод и считывание введенных данных:

a: array [1.20,1.20] of integer;

b: array [1.1000] of real;

g: array [1.20,1.20] of integer;

begin

write ('Введите коэфициенты при целевой функции: ');

readln (z1,z2);

write ('Количество уравнений '); readln (n);

write ('введите x3, x4,x5');

readln (x3,x4,x5);

for i: =1 to n do begin

for j: =1 to 2 do begin

write ('a', i,',', j,'= '); readln (a [i, j]);

end;

write ('b', i,'= '); readln (b [i]);

end;

write ('razmernost, ed mat');

readln (k);

for i1: =1 to k do begin

for j1: =1 to k do begin

if i1=j1 then g [i, j]: =1 else g [i, j]: =0;

write (g [i, j]: 5);

end;

writeln;

end;

6. Результаты применения программы

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

Рисунок 3. Результаты применения программы. Результат решения

Рисунок 4. Исходные данные

Рисунок 5. Полученная матрица

Рисунок 6. Результат работы

7. Ход статистического анализа

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

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

F=a_0,1x₁+a_0,2x₂+. a_0,nx_n +b₀ > max

a_1,1x₁+a_1,2x₂+. a_1,nx_n + x_n+1=b₁

a_2,1x₁+a_2,2x₂+. a_2,nx_n +x_n+2 =b₂

…

a_{m, 1}x₁+a_{m, 2}x₂+. a_{m, n}x_n+x_n+m=b_m

Для реализации симлекс-метода ЗЛП должна быть приведена к каноническому виду, т. е. к виду, где x1… xn — переменные ЗЛП xn+1…xn+m — балансовые переменные. Будем считать, что балансовые переменные можно взять в качестве базисных (выполняется условие неотрицательности xi)

Исходная таблица для задачи имеет следующий вид:

x₁, x₂, x_{n -} свободные переменные, x_n+1, x_n+2, x_n+m — дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы, а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.

Алгоритм симплекс-метода.

Подготовительный этап

Приводим задачу ЛП к каноническому виду

F=a_0,1x₁+a_0,2x₂+. a_0,nx_n +b₀ > max

a_1,1x₁+a_1,2x₂+. a_1,nx_n+x_n+1=b₁

a_2,1x₁+a_2,2x₂+. a_2,nx_n+x_n+2=b₂

…

a_{m, 1}x₁+a_{m, 2}x₂+. a_{m, n}x_n+x_n+m=b_m

В случае если в исходной задаче необходимо найти минимум — знаки коэффициентов целевой функции F меняются на противоположные a_0,n=-a_0,n. Знаки коэффициентов ограничивающих условий со знаком «?» так же меняются на противоположные. В случае если условие содержит знак «?» — коэффициенты запишутся без изменений.

Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче

Шаг 1. Проверка на допустимость.

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю — он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a_{k, l} — он задает ведущий столбец — l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам.

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

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

Шаг 2. Проверка на оптимальность.

На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строке F (не беря в расчет элемент b_{0 -} текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.

Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b₀)

a_0,l=min{a_{0, i} }

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

b_k/a_{k, l} =min {b_i/a_{i, l} } при a_{i, l}>0, b_i>0

k — cтрока, для которой это отношение минимально — ведущая. Элемент a_{k, l} — ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2

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

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

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

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

· Вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_lзаписываем x_k.

· ведущий элемент заменяется на обратную величину a_{k, l}'= 1/a_{k, l}

· все элементы ведущего столбца (кроме a_{k, l}) умножаются на — 1/a_{k, l}

· все элементы ведущей строки (кроме a_{k, l}) умножаются на 1/a_{k, l}

· оставшиеся элементы симплекс-таблицы преобразуются по формуле a_{i, j}'= a_{i, j} — a_{i, l}x a_{k, j}/ a_{k, l}

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

Преобразуемый элемент a_{i, j} и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».

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

Авторы аналогичных работ выполнил программную часть на языках программирования, таких как C#, C++, Qt. На языке программирования Pascal ABC реализовать решение уравнений симплекс методом получалось далеко не у всех.

Выводы

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

1. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. СПб — М.: Физматлит, 2011. — 630с.

2. Березин И. С., Жидков Н. П. Методы вычислений. — Т.1. — М.: Наука. 1966. — 632с.

3. Бобровский С. И. Delphi7. Учебный курс. — СПб.: Питер, 2003. — 736 с.

4. Волков Е. А. Численные методы. — М.: Наука, 1987. — 248с.

5. Дьяконов В. П. Справочник по алгоритмам и программам на языке бейсик для персональных ЭВМ. — М.: Наука, 2007.

6. Заварыкин В. М., Житомирский В. Г., Лапчик М. П. Численные методы. — М.: Просвещение, 1991. — 175с.

7. Информатика. Базовый курс.2-е издание/Под ред. С. В. Симоновича. — СПб.: Питер, 2010. — 640 с.

8. Копченова Н. В., Марон И. А. Вычислительная математика в примерах и задачах. — М.: Наука, 1972. — 366с.

9. Мудров А. Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. — М.: Наука, 2009. — 361с.

10. Пискунов Н. С. Дифференциальное и интегральное исчисления: Учебник для втузов. В 2-х т. Т.1: — М.: Интеграл — Пресс, 2001. — 416 с.

11. Ракитин В. И., Первушин В. Е. Практическое руководство по методам вычислений. [Текст]. — М.: Высшая школа, 1998. — 384с.

12. Турчак Л. И. Основы численных методов. [Текст]. — М.: Наука, 1987. — 318с.

13. Фаронов В. В. Delphi. Программирование на языке высокого уровня. Учебник для вузов. — СПб.: Питер, 2011. — 640 с.

Приложения

Приложение 1

Приложение 2