Лабораторные работы

по программированию для студентов

  • Увеличить размер шрифта
  • Размер шрифта по умолчанию
  • Уменьшить размер шрифта

Симплекс метод

E-mail Печать PDF

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

В данном материале рассмотрен пример реализации алгоритма симплекc метода на языке С++.

Более подробно о самом методе можно прочитать  на http://ru.wikipedia.org/wiki/Симплекс-метод.

Здесь же я продемонстрирую реализацию алгоритма симплекс метода на языке программирования высокого уровня C++.


Итак, имеем типовую задачу:

 

Для изготовления двух видов продукции P1,P2 используют три вида сырья S1,S2,S3. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, приведены в таблице 1.

Необходимо составить такой план выпуска продукции, чтобы при её реализации получить максимальную прибыль.

 

Организуем условие задачи в таблицу 1

Вид сырья

Запас сырья

Нормы расхода сырья на единицу выпуска

P1 P2
S1 20 2 5
S2 40 8 5
S3 30 5 6
Прибыль от единицы продукции, рублей 50 40

 

Задача линейного программирования, как и любая задача исследования операций включает в себя

1) Переменные которые следует определить

2) Целевую функцию подлежащую оптимизации

3) Ограничения, которым должны удовлетворять переменные

Итак оперделим

переменные для нашей задачи:

x1 - план выпуска продукции P1

x2 - план выпуска продукции P2

Целевая функция: величина общей прибыли Z=50*x1 +40*x2

Ограничения:

2*x1+5*x2<=20

8*x1+5*x2<=40

5*x1+6*x2<=30

Требуется определить x1,x2, максимизирующие целевую функцию Z.

Примечание: Без учета ограничения целочисленности результатов.

 

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

Пояснения к решению:

  • Свободные члены - это правая сторона ограничений для решаемой задачи
  • Коэффиценты - это числа стоящие перед переменными в ограничениях, а также в целевой функции, обратите внимание, что коэфиценты целевой функции вводятся в самом конце
  • Далее вводится знаки ограничений (больше или меньше), если в ограничении стоит знак "<", то вводим 0, если знак > то вводим 1, если знак =, то вводим 0
  • 8888 - это бесконечность, устанавливается при определенных условиях описанных в теории симплекс метода
  • Далее идет табличное вычисление оптимального значения функции
  • В решении мы видим X1, X2, X3 - X1 и X2 - это искомые переменные, X3 это добавочная переменная, которая генерируется в процессе табличного вычисления.

 

Купить исходный код симплекс метода на C++ через plati.ru (50 руб)

Обновлено 09.01.2014 07:01  

Добавить комментарий


Защитный код
Обновить


Поиск

Войти

Ваше мнение:

Нужно ли программисту учиться в университете?
 

Опрос

Кто круче?