Winni

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

Область применения:
  • Составить план выпуска продукции (в ассортименте), обеспечивающий максимальную прибыль при заданных ограниченных ресурсах (сырье, оборудование, раб.сила, указания вышестоящих инстанций)
  • Составить план перевозок груза из складов потребителям, обеспечивающий минимум суммарных затрат (например, минимум тонно-километров)
  • Другие аналогичные задачи (план перемещения грунта при выравнивании строительной площадки)
Возможности учебной (freeware) версии программы :
G - количество ограничений вида >= в системе ограничений - не более 15
E - количество ограничений вида = в системе ограничений - не более 15
L - количество ограничений вида <= в системе ограничений - не более 15
N - количество неизвестных - не более 30

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

Полная версия тестирована при N = 1000, L=500 на машине с оперативной памятью 256Мб.
Для приобретения полной версии свяжитесь с автором: Vlad-Alex_0@mail.ru

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

Прежняя (freeware) версия решает задачи размерностей (N< 200; G,L,E < 40), но выводит результаты, которые трудно понять.
Здесь инструкция к прежней версии


Вид программы ( таблица исходных данных учебной задачи )

Вид программы ( Результаты решения учебной задачи )

Текстовый отчет о результатах решения учебной задачи

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

Описание

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

Возможности учебной (freeware) версии программы составляют: 
- максимальное число неизвестных = 30  ( для студенческой версии. Испытано до 1000 )
- максимально ограничений каждого вида   = 15  ( для студенческой версии. Испытано до 500 )
- эти параметры можно увеличить при необходимости. 
 
Программа выполняет две проверки полученного решения: проверку допустимости решения и проверку
 оптимальности решения. Это делает полученные решения достоверными. 
Допустимость решения несложно проверить матричным умножением, а оптимальность – просмотром 
теневых цен и остатков ресурсов. 

Полная версия программы формально не имеет ограничений на значения G,E,L,N - всё зависит от объёма 
памяти компьютера. Программа тестирована при 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. 
Rambler's Top100
Hosted by uCoz