Курсовая работа (т): Решение типовых задач линейного программирования в табличном процессоре MS Excel

Получается, что величина a_ij это количество i-го элемента, присутствующего в единице веса j-го продукта. Матрица  называется матрицей питательности.

Вектор решения для рациона питания должен показать, какое количество x_i i-го продукта должно содержаться в меню«исследуемого» животного за день (месяц, квартал, год). Он означает, что за определенный промежуток времени животное должно быть обеспеченоx₁единиц первого продукта, x₂ единиц второго, …, x_n единиц n-го продукта.

Какие же требования могут быть предъявлены к рациону? Выполнение конкретных медицинских требований. Они состоят в том, что за определенный срок животное должно получить не менее необходимого количества каждого элемента. Обозначим через b_j, то минимально необходимое количество j-го элемента, которое должно получить животное. В таком случае, рацион питания должен соответствовать полученным ограничениям (2.1).

(2.1)

Тогда стоимость всей диеты будет составлять:

(2.2)

где  - цена единицы веса i-го продукта.

Очевидно, что затраты должны быть как можно меньше. Поэтому задача приобретает такой вид: найти рацион (2.2) минимальной стоимости при выполнении всех ограничений (2.1). Математически это выглядит так:

(2.3)

Таким образом, очевидно что:

-       реальная задача приобрела строгую математическую форму;

-       функция цели (стоимость питания) является линейной функцией;

-       ограничения на значения переменных x₁, x₂, …, x_n имеют вид системы линейных неравенств.

.2 Задача о составлении плана производства

Проанализируем производственную деятельность некоторой структурной единицы (филиал, отдел, подразделение и др.). Предположим, что конкретная производственная единица может выпускать некоторые продукты

Для выпуска данных товаров необходимо использовать различные материальные ресурсы. Пусть количество этих ресурсов будет m; обозначим их через

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

Таблица 2 - Технологическая матрица

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

(2.4)

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

(2.5)

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

.3 Задача о раскрое материалов

В нахождении наиболее рационального способа раскроя имеющегося материала, (металлические стержни, бумажное полотно, ткань и др.) состоит задача оптимального раскроя.

Нередко поиск оптимального способа раскроя осуществляется в два этапа.

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

На II этапе решаются задачи рациональных способов раскроя.

-       Нахождение рациональных способов раскроя материала

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

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

Пусть- индекс типа заготовки ();

 - номер способа раскроя единицы материала ();

 - количество заготовок вида , полученных при раскрое единицы материала -м способом.

Математически представить определение рационального способа раскроя материала можно в таком виде: способ раскроя  называется рациональным, если для любого другого способа раскроя  из соотношений , следуют соотношения  [5].

-       Определение интенсивности использования рациональных способов раскроя.

Обозначения:

 - индекс материала ();

 - номер типа заготовки ();

 - индекс способа раскроя единицы материала();

 - количество заготовок вида , полученных при раскрое единицы -го материала -м способом;

 - количество заготовок вида  в комплекте, отправляемому заказчику;

 - количество материала-го вида;

- количество единицу-го материала, раскраиваемых по -му способу (интенсивность использования способа раскроя);

- величина отхода, полученного при раскрое единицы -го материала по -му способу;

- число комплектов заготовок различного вида.

Имеется несколько типов моделей задач о раскрое материала:

-       Модель I(раскрой, с минимальным расходом материалов):

где (2.6) - функция цели (минимум количества используемых материалов);

(2.7) - система ограничений, определяющих количество заготовок, необходимое для выполнения работы;

(2.8) - условия неотрицательности переменных.

Модель II (раскрой, с минимальными отходами материалов):

где (2.9) - функция цели (минимум отходов при раскрое материалов);

(2.10) - система ограничений, определяющих количество заготовок, необходимое для выполнения заказа;

(2.11) - условия неотрицательности переменных.

-       Модель III (раскроя материала с учетом комплектации):

где (2.12) - функция цели (максимум комплектов, включающих заготовки различных видов);

(2.13) - ограничения по количеству материалов;

(2.14) - система ограничений, определяющих количество заготовок, необходимое для формирования комплектов;

(2.15) - условия неотрицательности переменных.

Рассмотрим несколько подробнее задачу о раскрое материала в общем виде.

Пусть на обработку поступает a единиц сырьевого материала одного вида (например, a листов картона одинаковых размеров). Из них необходимо изготовить комплекты, в каждый из которых входит n видов изделий в количестве, пропорциональном числам  Имеется m способов обработки данного материала, то есть известны величины  определяющие количество единиц j-х заготовок при i-м способе раскроя [18].

Установить план раскроя, при котором количество комплектов будет максимально. Согласно условиям задачи имеем, таблицу 3:

Таблица 3 -Способы раскроя

Пусть x_i- количество единиц сырьевого материала, раскраиваемого i-м вариантом

Тогда количество изделий 1-го вида равно:

Принимая во внимание условие комплектности, имеем:

где y - количество комплектов.

Аналогичные равенства можно записать и для всех остальных типов изделий, то есть условие комплектности приводит к системе ограничений:

.

Очевидно,  (на раскрой поступает a единиц сырьевого материала), а также

Цель задачи - максимизировать количество комплектов:

Итак, приходим к математической модели задачи о раскрое:

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