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

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

Эти возможности можно расширить. Eсли кому-нибудь нужно - cообщите об этом: Vlad-Alex_0@mail.ru
Однако не обижайтесь, если не отвечу - возможны проблемы со здоровьем. А обычно смотрю почту каждый вечер.

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

Вид программы (таблица исходных данных. )

Вид программы (Результаты)

Вид программы (Результаты решения задачи BigData2: N=1000, L=500 (фрагмент))

Описание

 

Обозначения: 
  G  - количество ограничений вида >= в системе ограничений   
  E  - количество ограничений вида  = в системе ограничений   
  L  - количество ограничений вида <= в системе ограничений     
  N  - количество неизвестных 
  Eps – требуемая точность ( допустимая погрешность)  

Возможности этой версии программы составляют: 
- максимальное число неизвестных = 30  ( для студенческой версии. Испытано до 1000 )
- максимально ограничений каждого вида   = 15  ( для студенческой версии. Испытано до 500 )
- эти параметры можно увеличить при необходимости.  
Программа выполняет две проверки полученного решения: проверку допустимости решения и проверку
 оптимальности решения. Это делает полученные решения достоверными. 
Допустимость решения несложно проверить матричным умножением, а оптимальность – просмотром 
теневых цен и остатков ресурсов. 
Возможности программы можно расширить во много раз, если кому-нибудь нужно. 
Программа тестирована при N = 1000, L=500 на машине с оперативной памятью 256Мб. 
При этом система использовала файл подкачки, но время решения было около 1 мин. 
В тестовой задаче требовалось обеспечить заданный минимум выпуска убыточного продукта (Х1) 
и получить максимальную прибыль от выпуска остальных 999 видов продукции при наличии 
499 ограничений на ресурсы (данные BigData2). 
Оптимальное допустимое решение получено.  
Для создания исходных данных большого объема использовалась специальная процедура 
(Меню | Файл | Генерировать тест-данные), которая заполняет файл BigData.dat, BigData.ogran  
BigData.neizv  случайными числами при заданных N, L, Eps. 
Программа тестировалась также на задачах небольшой размерности. 
Если Вам требуется модифицированная версия программы, свяжитесь c Winni: Vlad-Alex_0@mail.ru    
Вероятно, удобнее решать подобные задачи при помощи MS Excel. 
В 2005 г понадобилось решить учебную задачу, с 200 неизвестных 
(это была задача о перемещении масс грунта для выравнивания строительной площадки). 
Excel не справился с таким числом неизвестных. Возможно, сейчас он мощнее…
Программа решает все задачи одним методом – модифицированным симплекс методом, 
описанном в книге Банди «Основы линейного программирования», 
причем ищет минимум  целевой функции. Чтобы искать максимум, умножьте целевую функцию 
на –1, т е её коэффициенты. Полученное значение целевой функции 
– прибыль – нужно также умножить на -1  (см примеры) 
Для решения транспортных задач линейного программирования  существует вообще-то 
более рациональный алгоритм, но наша программа решает такие задачи общим способом. 
Отыскиваются коэффициенты целевой функции (они равны элементам матрицы тарифов), 
отыскивается матрица ограничений (например, вычисляется, сколько товара вывезено с каждого склада 
и это должно быть не больше наличия товара на этом складе) далее вычисляется, 
сколько товара завезено в каждый магазин, и это должно быть равно заявке этого магазина. 
Примерно так, хотя могут быть варианты. 
В одном из примеров решена транспортная задача, в которой с некоторого склада нужно было 
вывезти количество товара в заданных пределах ( см пример  ). 
Результаты решения выводятся на форме «Таблица результатов»: 
- таблица «Решение» содержит оптимальный план выпуска продукции. 
- окошко «Значение целевой функции» 
- таблица «Расход ресурсов и анализ ограничений». Здесь Вы видите расход каждого ресурса 
на выпуск каждого вида продукции. В правой части таблицы показан общий расход каждого 
вида ресурса в сравнении с имеющимися запасами. 
На форме есть кнопка «Текстовый отчет», открывающая форму с отчетом. 
Отчет можно сохранить в формате RTF, который открывается и может быть распечатан 
с помощью MS Word или системного редактора Wordpad.

Скачать Simka2009_stud.rar (333K)
(исполняемый файл программы, данные примеров, описание)

( Для скачивания:
1. Правый щелчок по ссылке
2. Выпадет контекстное меню. Выбрать: Сохранить объект как
3. В окне "Сохранить как" щелкнуть кнопку "Сохранить". )

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

Описание