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

Так как в строке вектора Р₃ нет отрицательных чисел, то исходная задача не имеет решения.

 

 
 

 

 

 

 

 

 

3 КОМПЬЮТЕРНАЯ РЕАЛИЗАЦИЯ СИМПЛЕКС-МЕТОДА ПРИ РЕШЕНИИ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

 

        3.1 описание программного продукта                  

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

- порождение начального базисного допустимого решения;                        

- поиск оптимального плана и экстремума нецелочисленной задачи линейного программирования;                                  

- поиск оптимального плана и экстремума полностью целочисленной задачи линейного программирования;                                                  

- поиск оптимального плана и экстремума частично целочисленной задачи линейного программирования;                                             

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

          Рассмотрим особенность функционирования программного комплекса. Для организации диалога с пользователем применяется стандартный графический интерфейс Windows, построенный на основе библиотеки визуальных компонентов VCL (VisualComponentLibrary), поставляемой вместе с пакетом Delphi. При разработке программы использовалась MDI-технология (MultipleDocumentInterface – многодокументный пользовательский интерфейс), что позволяет пользователю работать сразу с несколькими задачами линейного программирования. В программе реализована активная форма диалога, позволяющая выбирать режимы: расчет, просмотр и редактирование информации, получение справки и т.д. 
         Главное меню содержит следующие пункты: файл, правка, вид, вычисления, окно, справка. Все пункты главного меню вызывают подменю. В начале работы программы некоторые пункты запрещены и становятся разрешенными только по мере выбора других пунктов меню (например, меню «Правка», «Вычисления» и т. д.)                                                                

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

 

          3.2 Тестирование программного продукта                  

 – Поиск максимизирующего прибыль плана производства                    

 –Поиск максимизирующего прибыль плана производства                         

 –  Оптимальный план производства                                                        

 
ЗАКЛЮЧЕНИЕ 

 

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

Задачи линейного  программирования решаются несколькими  методами: 
         - графический метод;                         

- симплекс-метод;                                                       

- двойственный симплекс-метод.                                                  

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 
 

1. Павлова Т. Н. Линейное программирование: учеб.пособие / Т. Н. Павлова, О. А. Ракова. – Д.: 2002. 
2. БерюховаТ.Н.Банк производственных задач в расчетах на ЭВМ: учебное пособие. – Тюмень.: ТюмИИ, 1992. – 124с.  
     Карманов В.Г. Математическое программирование: учебное пособие для студентов вузов. – М.: Физматлит, 2001. – 264с.  
3. Кузнецов А.В. Математическое программирование: учебное пособие для вузов. – М.: Высшая школа, 1976. – 352с.  
4. Мочалов И.А. Нечеткое линейное программирование. // Промышленные АСУ и контроллеры. – 2006. - № 10. – с.26-29.  
5. Пашутин С.Оптимизация издержек и технология формирования оптимального ассортимента. // Управление персоналом. – 2005. - №5. – с.20-24. 
6. Жиглявский А.А., Жилинкас А.Г. Методы поиска глобального экстремума. — М.: Наука, Физматлит, 1991.
7. Карманов В.Г. Математическое программирование = Математическое программирование. — Изд-во физ.-мат. литературы, 2004.
8. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
9. Сайт http://ru.wikipedia.org/wiki
10. Сайт http://revolution.allbest.ru
11. Сайт http://fessagicadif.web44.net
12. http://www.math.mrsu.ru/text/courses/method/dvoistvennii_simplex.htm