Полагая x_n+1=x_n+2=…=x_m=0, получим: 

               

       Если  окажется, что x₁³0, x₂³0, …, x_m³0, то совокупность чисел (x₁, x₂, …, x_n, 0, 0, …, 0) дает неотрицательное решение системы.

       Рассмотрим  пример. Дана система уравнений 

         

       Нужно данную систему разрешить относительно переменных x₁, x₂, x₃. Следовательно свободными переменными будут x₄, x₅, x₆. Напишем таблицу, соответствующую данной системе уравнений. 

         

       Решим систему относительно x₁ с помощью первого уравнения. За разрешающий элемент принимаем первый элемент первой строки, и подвергнем таблицу S-преобразованию. Получим новую таблицу, где первая строка переписывается, в первом столбце записываются нули, а остальные элементы вычисляются по D-правилу. 

         

       Этой таблице соответствует система уравнений, разрешенная относительно x₁ (x₁ входит только в первое уравнение). Исключить x₂ удобнее с помощью третьего уравнения, так как коэффициент при x₂ в третьем уравнении равен единице. Принимаем его за разрешающий элемент. Пишем новую таблицу 

         

       Система уравнений, соответствующая этой таблице, разрешена относительно x₁ и x₂ (x₁ входит только в первое уравнение, а x₂ только в третье).

       Для разрешения системы относительно x₃ за разрешающий элемент берем коэффициент при x₃ во втором уравнении. Новая таблица имеет вид 

         

       Последняя таблица соответствует системе, решенной относительно базисных переменных x₁, x₂, x₃. Полагая свободные переменные x₄, x₅, x₆ равными нулю, получим уравнения: 

       -3x₁=-18, откуда x₁=6

       -3x₂=-6, откуда x₂=2

       -3x₃=3, откуда x₃=-1 

       Совокупность  чисел x₁=6, x₂=2, x₃=-1, x₄=0, x₅=0, x₆=0 есть одно из решений данной системы. Оно не принадлежит к области допустимых решений, так как одна из координат x₃ отрицательна.

       Для решения задачи линейного программирования важно уметь находить неотрицательные (опорные) решения данной системы уравнений. 

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

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

          (1.19) 

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

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

       Рассмотрим  пример отыскания неотрицательных  решений системы уравнений.

       Пример. Найти неотрицательное решение  системы уравнений 

         

       Пишем таблицу, соответствующую данной системе 

         

       Пробуем разрешить эту систему относительно x₁, т.е. переменную x₁ будем считать базисной переменной. Первый столбец будет базисным столбцом. Составляем отношения свободных членов к положительным элементам первого столбца 10/2=5; 4/7. Наименьшее из этих чисел 4/7. Числа 4 и 7 находятся во второй строке. Следовательно разрешающей строкой будет вторая строка и разрешающим элементом число 7. Выполняя симплекс преобразование, получим новую таблицу 

         

       Этой  таблице соответствует система  уравнений, разрешенная относительно базисной переменной x₁. Так как обе части любого уравнения системы можно умножать и делить на любое постоянное число (система при этом будет эквивалентна прежней), то если строки таблицы имеют общий множитель, на него можно сократить. Последняя строка предыдущей таблицы имеет общий множитель 7; сокращая на него, получим таблицу 

         

       Введем  в базис переменную x₃, т.е. примем за разрешающий столбец третий столбец.

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

         

       Первую  строку сокращаем на 28, вторую на 21

         

       Введем  в базис переменную x₂. Разрешающим элементом будет 5. Снова выполняя симплекс преобразования, получим таблицу 

         

       Последнюю строку сокращаем на 3 

         

       Эта таблица соответствует системе  уравнений, разрешенной относительно базисных переменных x₁, x₂, x₃. Свободными переменными здесь являются x₄ и x₅. Полагая свободные переменные равными нулю, получим:

       5x₁=12, x₁=12/5; 5x₂=2, x₂=2/5; 5x₃=18, x₃=18/5;

       Совокупность  чисел x₁=12/5; x₂=2/5; x₃=18/5; x₄=0; x₅=0

       Дает  неотрицательный ответ данной системы уравнений. Эти числа можно рассматривать как координаты угловой точки (вершины) множества (многогранника) допустимых решений.

       1.4 Обоснование выбора метода решения задачи линейного программирования.

       Симплекс  метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.

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

1. Ограничения вида  «£»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».
2. Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1» , а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).
3. Ограничения вида «³» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.

       2 Разработка алгоритма  решения задачи линейного программирования

 

         
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       Рисунок  2.1  Блок- схема алгоритма симплекс метода 
 

       3 Руководство пользователя к программе

       3.1 Назначение и условия применения программы

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

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

       Программа Решение задачи линейного программирования представляет собой многодокументное приложение Windows, реализованное с помощью аппаратных средств IBM PC ATX с операционной системой Windows XP и программных средств Borland Delphi 7.0.

       Программа является 32 разрядным приложением  и требует установленной  32 разрядной операционной системы Windows 9x/2000/Me/XP. Наличие принтера является необязательным.

       3.2 Характеристики программы

       Программа занимает 988 Кбайт дискового пространства. Для организации диалога с пользователем используется стандартный графический интерфейс Windows, построенный на основе библиотеке визуальных компонентов VCL (Visual Component Library), поставляемой вместе с пакетом Delphi. При разработке программы использовалась MDI-технология (Multiple Document Interface – многодокументный интерфейс), что позволяет пользователю работать сразу с несколькими задачами линейного программирования.

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

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

       

 

       Рисунок 3.1 – Диалоговое окно программы

       3.3 Обращения к программе

       Исполняемый файл программы имеет имя Решение задачи линейного программирования.exe. Вычислительные модули нецелочисленного и целочисленного программирования встроены в программу и вызываются соответственно командами «Симплекс-метод».

        3.4 Входные и выходные данные

        
 
 
 
 
 
 

 
 

       Рисунок 3.2 Ввод параметров задачи 

       Входными  данными программы является целевая функция, максимум или минимум которой требуется найти и система линейных ограничений. Для ввода коэффициентов используется редактор задачи, показанный на рисунке 3.1, позволяющий добавлять функцию и ограничения, изменять и удалять их. Окно параметров задачи содержит две вкладки: вкладка «Функция», служащая для изменения целевой функции и вкладка «Ограничения» рисунок 3.2, для редактирования линейных ограничений. Для удобства в программе не требуется кодирования входных данных. Обработка и машинное представление входных данных производится автоматически.

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

       Результаты  решения задачи показаны на рисунке 3.3

         
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       Рисунок 3.3 Ввод параметров задачи 

       Существует  возможность сохранить на диске  как входные данные, так и выходные для последующего считывания. Эти  операции выполняются командами  «Открыть…», «Сохранить» и «Сохранить как…» главного меню приложения. Диалоговые окна сохранения и загрузки данных имеют стандартный вид и позволяют совершать файловые операции.