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

Среди неотрицательных решений системы неравенств:

найти такое, при котором линейная форма достигает наименьшего значения.

Решение. Систему неравенств путем введения дополнительных переменных сводим к системе уравнений:

и подвергаем тождественным преобразованиям:

Одним из неотрицательных решений системы неравенств является решение Выразим теперь линейную форму через неосновные переменные:

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

Для пошива одного изделия требуется выкроить из ткани 6 деталей.

На швейной фабрике были разработаны два варианта раскройки ткани. В таблице (расположенной ниже) приведены характеристики вариантов раскроя 10 м² ткани комплектность, т. е. количество деталей определенного вида, которые необходимы для пошива одного изделия. Ежемесячный запас ткани для пошива изделий данного типа составляет 405 м². В ближайший вечер планируется сшить 90 изделий.

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

Таблица 1

Характеристики вариантов раскроя отрезков ткани по 10 м.

В данной задаче искомые величины явно не указаны, но сказано, что должен быть выполнен ежемесячный план по пошиву 90 изделий. Для пошива 90 изделий в месяц требуется раскроить строго определенное количество деталей. Крой производится из отрезков ткани по 10 м² двумя различными способами, которое позволяют получить различное число деталей. Поскольку заранее неизвестно, сколько ткани будет раскраиваться первым способом и сколько — вторым, то в качестве искомых величин можно задать количество отрезков ткани по 10 м², раскроенных каждым из способов:

— количество отрезков ткани по 10 м², раскроенных первым способом в течении месяца, [отрез./мес.];

— количество отрезков ткани по 10 м², раскроенных первым способом в течение месяца, [отрез./мес.];

Целевая функция:

Целью решения задачи является выполнение плана при минимальном количестве отходов. Поскольку количество изделий строго запланировано (90 шт./мес.), то этот параметр не описывает ЦФ, а относится к ограничению, невыполнение которого означает, что задача не решена. А критерием эффективности выполнение плана служит параметр «количество отходов», который необходимо свести к минимуму. Поскольку при раскрое одного отреза (10м²) ткани по 1-му варианту получается 0,5 м² отходов, а по 2-му варианту — 0,35 м² (см. таблицу 1), то общее количество отходов при крое целевая функция имеет вид:

[].

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

Количество раскроев ткани различными способами ограничивается следующими условиями:

• · Должен быть выполнен план по пошиву изделий, другими словами, общее количество выкроенных деталей должно быть таким, чтобы из него можно было пошить 90 изделий в месяц, а именно: 1-го вида должно быть как минимум 90 и деталей остальных видов — как минимум по 180 (см. комплектность в табл.1).
• · Расход ткани не должен превышать месячного запаса на складе;
• · Количество отрезков раскроенной ткани не может быть отрицательным.

Ограничение по плану пошива пальто имеют следующую содержательную форму записи.

• (Общее количество деталей № 1 выкроенных по всем вариантам)(90 штук);
• (Общее количество деталей № 2 выкроенных по всем вариантам)(180 штук);
• (Общее количество деталей № 6 выкроенных по всем вариантам)(180 штук);

Математически эти ограничения записываются в виде:

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

Содержательную:

(общее количество ткани, раскроенной за месяц)(405м²).

Математическую:

Не отрицательность количества раскроенных отрезков задается в виде:

Таким образов, математическая модель задачи имеет вид:

.