Применение двойственного симплекс-метода для составления оптимального плана производств

 

 

 

 

 

 

Задание

На курсовое проектирование по дисциплине

“Математические Методы”

Тема задания  “ Применение двойственного симплекс-метода для составления оптимального плана  производств”.

 

Москва 2012

Часть I. Пояснительная  записка.

Титульный лист.

Задание на курсовое проектирование.

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

Оглавление.

Основная часть.

 

• Теоретические основы.

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

(54)

при условиях

(55)

(56)

где

и среди чисел  имеются отрицательные.

В данном случае  есть решение системы линейных уравнений (55). Однако это решение не является планом задачи (54) – (56), так как среди его компонент имеются отрицательные числа.

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

 

 

Определение 14.

Решение  системы линейных уравнений (55), определяемое базисом  , называетсяпсевдопланом задачи (54) – (56), если  для любого 

Теорема 11.

Если в псевдоплане  , определяемом базисом  , есть хотя бы одно отрицательное число  такое, что все  , то задача (54) – (56) вообще не имеет планов.

Теорема 12.

Если в псевдоплане  , определяемом базисом  , имеются отрицательные числа  такие, что для любого из них существуют числа a_ij<0, то можно перейти к новому псевдоплану, при котором значение целевой функции задачи (54) – (56) не уменьшится.

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

Итак, продолжим рассмотрение задачи (54) – (56). Пусть  – псевдоплан этой задачи. На основе исходных данных составляют симплекс-таблицу (табл. 15), в которой некоторые элементы столбца вектора  являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (54) – (56), поскольку, по предположению, все  . Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс–таблицы к другой до тех пор, пока из столбца вектора  не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)–й строки, т.е.  для любого 

Таким образом, после  составления симплекс-таблицы проверяют, имеются ли в столбце вектора  отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются (что мы и предполагаем), то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое–нибудь одно из них: пусть это число b_l. Выбор этого числа определяет вектор, исключаемый из базиса, т. е. в данном случае из базиса выводится вектор P_l. Чтобы определить, какой вектор следует ввести в базис, находим  , где 

Пусть это минимальное  значение принимается при  , тогда в базис вводят вектор Р_r. Число  является разрешающим элементов. Переход к новой симплекс–таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р₀ не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i–й строке симплекс–таблицы (табл. 15) в столбце вектора Р₀ стоит отрицательное число b_i, а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.

Таким образом, отыскание решения задачи (54) – (56) двойственным симплекс-методом включает следующие этапы:

1. Находят псевдоплан задачи.

2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.

3. Выбирают разрешающую  строку с помощью определения  наибольшего по абсолютной величине  отрицательного числа столбца  вектора Р₀ и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)–и строки к соответствующим отрицательным элементам разрешающей строки.

4. Находят новый псевдоплан и повторяют все действия начиная с этапа 2.

 

 

 

 

 

Таблица 15

 

 

 

2. Практическая задача.

2.1. Постановка задачи

Применить  двойственный симплекс-метод для составления  оптимального плана производств.

2.2. Математическая модель.

таблица

2.3. Решение задачи.

 

3. Разработка программного обеспечения.

Разработка  программного обеспечения на Delphi с  помощью 

3.1. Описание входных данных.

3.2. Описание выходных данных.

3.3. Описание основных функций программного обеспечения.

3.4. Руководство пользователя.

Ввод входных  данных реализует

4. Проведение исследования. Решение практической задачи

Из отходов производства предприятие может организовать выпуск четырёх видов продукции. Для этого оно планирует использовать два типа взаимозаменяемого оборудования. Количество изделий каждого вида, которое может быть изготовлено на соответствующем оборудовании в течение 1 ч, а также затраты, связанные с производством одного изделия.

Оборудование I типа предприятие может использовать не более 80 ч, а               оборудование II типа – не более 60 ч.

Учитывая, что предприятию  следует изготовить изделий каждого  вида соответственно не меньше 240, 160, 150 и 220 ед., определить, в течение какого времени и на каком оборудовании следует изготовлять каждое из изделий так, чтобы получить не менее нужного количества изделий при минимальных затратах на их производство.

 

Вывод.

Заключение.

Список используемой литературы.

 

Приложения.

1.Распечатка вычислительной программы.

2. Материалы решения практической задачи.

3. Материалы проведения исследования.

 

Часть II. Практическая часть.

1. Блок-схема вычислительной программы.

2. Графические материалы решения задач.

3. Графические материалы проведения исследования.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Часть III. Отзыв  преподавателя.

______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________