Линейное программирование (Графический метод. Симплексный метод) (стр. 10 )

Этапы симплексного метода:

1)  Находят опорный план.

2)  Составляют симплекс-таблицу.

3)  Проверяют план на оптимальность с помощью оценок . Если среди них нет отрицательных оценок, то план оптимален. Если среди этих чисел имеются отрицательные, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.

4)  Находят направляющие столбец и строку, разрешающий элемент.

5)  Определяют элементы новой симплекс-таблицы.

6)  Проверяют найденный опорный план на оптимальность.

Вопросы:

1)  В чем заключается идея симплексного метода?

2)  Дайте определение допустимого базисного решения?

3)  В каком случае решение называется вырожденным?

4)  Какая связь существует между допустимыми базисными решениями задачи линейного программирования и угловыми точками области допустимых решений системы ограничений задачи?

5)  Назовите признак оптимальности опорного плана.

6)  Назовите признак бесчисленного множества оптимальных планов.

Упражнения

Решить задачу линейного программирования симплексным методом (с помощью симплексных таблиц)

17 ; .	18 ; .
19 ; .	20 ; .

Ответы и решения

1.1

1  Составим экономико-математическую модель задачи.

Обозначим искомые переменные следующим образом:

х1 - количество единиц продукции вида П1,

х2 - количество единиц продукции вида П2 планируется выпустить.

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

Доход предприятия от реализации единиц продукции вида и единиц продукции вида задает выражение .

Итак, экономико-математическая модель задачи имеет вид

2  Составим экономико-математическую модель задачи.

Обозначим искомые переменные следующим образом:

х1 - количество потребления корма вида П1,

х2 - количество потребления корма вида П2 в составе дневного рациона каждого животного.

В результате потребления х1 ед. корма вида П1 и х2 ед. корма вида П2 общее содержание питательного вещества А в рационе определяется выражением . Содержание питательного вещества А в рационе не должно быть меньше минимальной суточной потребности организма, т. е. величины 13, поэтому должно выполняться неравенство . Аналогично, получаем ограничение неравенство для вещества В : . Общее содержание вещества С должно быть не более 68 усл. ед. Это требование выражается в виде следующего неравенства: . Поскольку количество потребляемых кормов не может быть отрицательным, то должно выполняться условие . Стоимость рациона питания животных определяет выражение .

Итак, экономико-математическая модель задачи имеет вид

3  Составим экономико-математическую модель задачи.

Обозначим искомые переменные следующим образом:

х1 - количество единиц продукции вида П1,

х2 - количество единиц продукции вида П2 планируется выпустить.

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

Доход предприятия от реализации единиц продукции вида и единиц продукции вида определяется выражением .

Итак, экономико-математическая модель задачи имеет вид

4  Составим экономико-математическую модель задачи.

Обозначим искомые переменные следующим образом:

х1 - количество станков вида 3СБШ,

х2 - количество станков вида 6СБШ планируется выпустить.

Производство х1 и х2 станков потребует расход металлопроката в объеме . Запас металлопроката на заводе ограничен 77 усл. ед, поэтому должно выполняться следующее неравенство . Аналогично, ограничение по расходам труб имеет вид , а неравенство выражает требование не превышения расходов запаса чугунов на производство запланированного объема продукции.

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

Доход предприятия от реализации станков вида 3СБШ и станков вида 6СБШ задает выражение .

Итак, экономико-математическая модель задачи имеет вид

5  ; .	6  ; .
7  ; .	8  ; .
9  ; .

1.2