Методические указания по решению злп в среде Exсel

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

Тверской государственный технический университет

 

 

Линейное программирование.

Примеры решения задач в Excel.

Тверь

Методическое пособие предназначено для студентов специальности «Экономика и управление на предприятии (машиностроение)», изучающих курсы «Экономико-математические методы в управлении» и «Экономико-математические модели объектов отрасли». Пособие можно также рекомендовать студентам экономических специальностей, изучающих экономико-математические методы и модели.

Обсуждено и рекомендовано на заседании кафедры ИПМ (протокол № от марта 2008 г.)

Составители: Е.Е. Фомина, И.Л. Кислова

 

© Тверской государственный технический университет, 2008

 

СОДЕРЖАНИЕ

Введение. 4

1 Методические указания по решению ЗЛП в среде Exсel 7

1.1 Максимизация прибыли предприятия. 7

1.2 Максимизация годового дохода. 17

1.3 Специальные задачи линейного программирования. 25

1.3.1 Задача целочисленного программирования. 25

1.3.2 Транспортная задача. 26

1.3.2.1 Закрытая транспортная задача. 27

1.3.2.2 Открытая транспортная задача. 34

1.3.3 Задача о назначениях. 35

1.3.4 Двойственность в задачах линейного программирования...36

2. Вопросы для самоконтроля. 47

3. Варианты заданий. 48

4. Требования к оформлению контрольной работы.. 59

Использованная литература. 60

 

 

Введение

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

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

 

Общая задача оптимизации

В общем виде математическая постановка задачи математического программирования состоит в определении наибольшего или наименьшего значения целевой функции f (x_1, x _{2, ….} x _n) при условиях g_i (x₁ , x_2,…, x _n) ≤ b_i; (i = 1,2, … m), где f и g_i - заданные функции, а b_i - некоторые действительные числа.

Задачи математического программирования делятся на задачи линейного и нелинейного программирования. Если все функции f и g_i - линейные, то соответствующая задачи является задачей линейного программирования (ЗЛП). Если хотя бы одна из указанные функций – нелинейная, то соответствующая задача является задачей нелинейного программирования.

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

Cреди задач нелинейного программирования наиболее глубоко изучены задачи выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве.

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

Отдельными классами задач математического программирования являются задачи целочисленного, параметрического и дробно-линейного программирования.

В общем виде задачи линейного программирования (ЗЛП) ставится следующим образом:

Необходимо найти вектор , максимизирующий линейную форму

(1)

и удовлетворяющий условиям

(2)

, (3)

где , , - действительные числа.

 

Линейная функция f(X) называется целевой функцией задачи. Условия (2) называются функциональными, а (3) – прямыми ограничениями задачи.

Вектор X=(x_1, x_{2, …} x_n), компоненты которого удовлетворяют функциональным и прямым ограничениям задачи, будем называть планом, или допустимым решением ЗЛП.

Все допустимые решения образуют область определения задачи линейного программирования, или область допустимых решений.

Допустимое решение, максимизирующее целевую функцию f (X), называется оптимальным планом задачи.

Будем считать, что ЗЛП записана в канонической форме, если ее целевая функция максимизируется, ограничения имеют вид равенств с неотрицательной правой частью и все переменные неотрицательные.

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

Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана, или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).

Выбор конкретной вычислительной процедуры осуществляется после приведения исходной задачи к каноническому виду задачи линейного программирования (КЗЛП):

 

В теории линейного программирования показано, что оптимальное решение ЗЛП связано с угловыми (крайними) точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А₁,А₂, …..А_n. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний C_m.

Решение ЗЛП симплекс-методом «вручную» подробно рассмотрено в [1], [5] и др.

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

· определения оптимальной производственной программы;

· оптимального смешивания компонентов;

· оптимального раскроя;

· оптимального размещения предприятий некоторой отрасли на определенной территории;

· формирования оптимального портфеля ценных бумаг;

· транспортной задачи и др.

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

 

Огромный вклад в развитие и применение ЗЛП внес наш соотечественник Леонид Витальевич Канторович. За что в 1975 г. Был удостоен Нобелевской премии по экономике.

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

Для выпуска 4 - х видов продукции требуется сырье, рабочее время и оборудование.

Для выпуска одной единицы продукции 1 - ого вида необходимо 3 ед. сырья, 22 ед. рабочего времени и 10 ед. оборудования.

Для выпуска одной единицы продукции 2 - ого вида необходимо 5 ед. сырья, 14 ед. рабочего времени и 14 ед. оборудования.

Для выпуска одной единицы продукции 3 - его вида необходимо 2 ед. сырья, 18 ед. рабочего времени и 8 ед. оборудования.

Для выпуска одной единицы продукции 4 - ого вида необходимо 4 ед. сырья, 30 ед. рабочего времени и 16 ед. оборудования.

Прибыль от продажи одной единицы продукции 1 - ого вида 30 руб., 2 - ого вида – 25 руб., 3 - его вида – 8 руб., 4 - ого вида – 16 руб.

Ресурсы ограниченны: имеется 60 ед. сырья, 400 ед. рабочего времени и 120 ед. оборудования.

А) Какое количество продукции каждого вида необходимо выпустить, чтобы максимизировать прибыль предприятия?

Б) Все ли продукты вошли в оптимальный план или существуют убыточные? На сколько нужно увеличить прибыль от продажи одной единицы убыточной продукции, чтобы она вошла в оптимальный план?

В) Каковы интервалы устойчивости для прибыли за одну единицу продукции каждого вида? Изменится ли оптимальное решение, если прибыли от продажи одной единицы продукции 4 – ого вида увеличить на 15 ед., 33 ед.? Уменьшить на 10 ед.?

Г) Какие ресурсы являются дефицитными? Как изменится оптимальное решение, если ресурс оборудование увеличить на 1 ед., уменьшить на 100 ед., 50 ед.?

 

Для удобства сведем данные задачи в следующую таблицу:

Таблица 1

Тип ресурса	Нормы затрат ресурса на одну единицу продукции	Наличие ресурсов (ед.)
Сырье
Рабочее время
Оборудование
Прибыль (руб.)

Решение

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

Т.к. цель задачи – максимизировать прибыль от продажи продукции (Р), то Р будет иметь вид:

Р=30*x₁+25*x₂+8*x₃+16* x₄ (руб.) (*)

Ограничения

Исходя из выражения для целевой функции, можно увидеть, что чем больше будут значения x₁, x₂, x₃,x₄, тембольше будет прибыль Р.

Однако беспредельно увеличивать выпуск продукции невозможно, т.к. ресурсы предприятия ограничены, что приводит к ограничениям на x₁, x₂, x₃,x₄.

3*x₁+5*x₂+2*x₃+4*x₄ 60, (1)

22*x₁+14*x₂+18*x₃+30*x₄ 400, (2)

10*x₁+14*x₂+8*x₃+16*x₄ 120, (3)

xi 0, i=1,2,3,4, (4)

Примечание:

· В левой части i-ого i=1,2,3 функционального ограничения записано общее количество ресурса i-ого i=1,2,3 вида (сырья, рабочего времени и оборудования), необходимого для производства всей продукции.

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

· Прямые ограничение (4) представляет собой следующее естественное условия: количество единиц выпускаемой продукции должно быть не отрицательным.

Таблица 2

Неизвестные
x1 –количество единиц продукции 1 - ого вида, x2 –количество единиц продукции 2 - ого вида, x3 –количество единиц продукции 3 - его вида, x4 –количество единиц продукции 4 - ого вида.
Целевая функция	Ограничения
Р=30*x1+25*x2+8*x3+16* x4 (руб.)	3*x1+5*x2+2*x3+4*x4 60, 22*x1+14*x2+18*x3+30*x4 400, 10*x1+14*x2+8*x3+16*x4 120, xi 0, i=1,2,3,4

Ответ

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

При этом максимальная прибыль составит 360 руб. .

Рис. 9 результат решения задачи

Таблица 3

Раздел Изменяемые ячейки

Столбец	Значение	Комментарии и примеры
Ячейка	Адреса ячеек с неизвестными
Имя	Имена неизвестных
Результирующее значение	Оптимальные значения неизвестных, полученные в ходе решения задачи.	Равенство нулю переменных х2, х3, х4 означает, что данная продукция является убыточной, т.е. стоимость ресурсов, затраченных на производство одного изделия, больше чем цена продукта.
Нормированная стоимость	Если продукт входит в оптимальный план, в столбце Нормированная стоимость для этого продукта стоит 0. Если продукт не входит в оптимальный план, то в этом столбце стоит отрицательное число, абсолютная величина которого показывает на сколько нужно увеличить прибыль от продажи единицы этого продукта, чтобы он вошел в оптимальный план.	Пример: Продукция второго вида не вошла в оптимальный план. Если увеличить прибыль от продажи продукции на 17 ед., т.е. она составит 25+17=42 ед., то станет выгодно выпускать изделия второго вида и оптимальное решение будет следующим = (0, 8,57, 0, 0), =360 руб. Аналогичные расчеты можно проделать для 3 – его и 4 – ого продукта.
Целевой коэффициент	Коэффициенты, стоящие при неизвестных в целевой функции.	В данной задаче – прибыль от продажи 1-ой единицы каждого вида продукции.
Допустимое увеличение Допустимое уменьшение	Числа, показывающие, на сколько максимально можно увеличить или уменьшить прибыль от реализации единицы продукции данного вида при сохранении оптимального плана выпуска. Оптимальное значение ЦФ при этом может изменится.	Примечание: Число 1Е+30 (10 ^+30 - максимально известное компьютеру число) означает, что прибыль можно уменьшать (увеличивать) практически не ограниченно, но при этом оптимальное решение останется прежним.   Анализ полученных значений: Т.о. получены следующие интервалы устойчивости: продукция 1 вида – (30+ 1Е+30, 30- 12,142), продукция 2 вида – (25+ 17, 25- 1Е+30), продукция 3 вида – (8+ 16, 8- 1Е+30), продукция 4 вида – (16+ 32, 16- 1Е+30). Пример: Для продукции четвертого вида допустимое увеличение 32, а допустимое уменьшение не ограниченно. Если увеличить прибыль от реализации единицы продукции данного вида на 15, т.е. она составит 16+15=31 руб., при этом оптимальное решение задачи не изменился =(12, 0, 0, 0), = 360 руб. Аналогично, при снижении прибыли на 10 руб. оптимальное решение осталось прежним. Если прибыль увеличить на 33 руб., т.е. она составит 16+33=49, то оптимальное решение изменится следующим образом: = (0, 0, 0, 7,5), =367,5 руб.

Таблица 4

Раздел Ограничения

Столбец	Примечание	Комментарии и примеры
Ячейка	Адреса ячеек с левыми частями ограничений
Результирующее значение	Значения левых частей ограничений в результате решения задачи
Теневая цена	Теневая цена показывает насколько изменится прибыть от производства всей продукции при увеличении правой части ограничения на 1 единицу (в рассматриваемой задачи – запаса данного ресурса на 1 единицу). + где - теневая цена. Теневая цена, также определяет ценность ресурса для производителя, если она отлична от 0, то ресурс считается дефицитным.	Пример: В нашем случае дефицитным ресурсом является оборудование (т.к. его теневая цена отлична от нуля) =3. Также, исходя из ограничения (3), видно, что оборудование использовано на 100 % (левая часть ограничения равна правой), в то время как остальные ресурсы использованы не полностью (левая часть ограничения меньше правой). Пример: Если дефицитный ресурс оборудование увеличить на 1 ед., то оптимальная прибыль изменится и станет равной =360+3=363 руб.
Ограничение правая часть	Значения правых частей ограничений
Допустимое увеличение	Число, показывающие, на сколько можно увеличить запасы ресурса при сохранении его теневой цены. При этом значение целевой функции изменится следующим образом: + , где -величина увеличении ресурса, - теневая цена.	Пример: Если увеличить ресурс оборудование на = 50 ед., то оптимальная прибыль составит = =360+50*3=510 руб.
Допустимое уменьшение	Число, показывающие, на сколько можно уменьшить запасы ресурса при сохранении его теневой цены. При этом значение целевой функции изменится следующим образом: - , где -величина увеличении ресурса, - теневая цена.	Пример: Если уменьшить ресурс оборудование на = 100 ед., то оптимальная прибыль составит = =360-50*3=60 руб.

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

 

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

Вкладчик располагает суммой в размере 50000 руб.

Банки города предлагают следующие проценты по вкладам:

1 банк – 8,5% годовых,

2 банк – 7% годовых,

3 банк – 8% годовых.

Вкладчик хочет распорядиться деньгами следующим образом:

1. Вся сумма должна быть вложена,

2. Не менее 55% суммы должно быть вложено во 2 банк,

3. В 3 банк должно быть вложено по крайней мере столько же, сколько и в 1 банк.

А) Каким образом распределить деньги, чтобы получить максимальный годовой доход?

Б) Каковы интервалы устойчивости процентных ставок банков?

В) Как изменится годовой доход, если вкладчик внесет дополнительные средства?

Решение

Элементы модели

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

Т.к. цель задачи – максимизировать общий годовой доход (D), то D будет иметь вид:

D=x₁*8,5%+x₂*7%+x₃*8% (руб.) (**)

Ограничения

Из предлагаемых процентных ставок банков видно, что чем больше денег будет вложено в 1 банк, тем больше будет годовой доход. Однако, вкладчик выдвигает ряд требований при вложении денег, что приводит к ограничениям на значения неизвестных x₁, x₂, x₃.

x₁+x₂+x₃=50000, (5)

x₂ (x₁+x₂+x₃)*55%, (6)

x₁ x₃, (7)

x_i 0, i=1,2,3 (8)

Примечание:

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

· В ограничении (2) фигурирует знак , т.к. во второй банк должно быть вложено не менее 55% от общей суммы денег.

· Аналогично, в ограничении (3) стоит знак , т.к. в 3 банк вкладывается по крайней мере столько же, сколько и в 1 банк.

· Ограничение (4) представляет собой следующее естественное условие: количество денег, вкладываемое в каждый банк, должно быть не отрицательным.

Таблица 5

Неизвестные
x1 (руб.) – количество денег, которые вкладчик вложит в 1 банк, x2 (руб.) – количество денег, которые вкладчик вложит во 2 банк, x3 (руб.) – количество денег, которые вкладчик вложит в 3 банк.
Целевая функция	Ограничения
D=x1*8,5%+x2*7%+x3*8% (руб.)	x1+x2+x3=50000, x2 (x1+x2+x3)*55%, x1 x3, xi 0, i=1,2,3

Ответ

В результате решения задачи был получен следующий ответ: В первый банк необходимо вложить 11250 руб., во второй банк – 27500 руб., в третий банк – 11250 руб. =(11250,27500,11250).

При этом максимальный годовой доход составит 3781,25 руб. =3781,25.

 

 

Рис. 19 результат решения задачи

Анализ решения

Используя данные отчета по устойчивости (см. рис. 20) проанализируем полученное решение.

Рис. 20 Отчет по устойчивости

Таблица 6

Раздел Изменяемые ячейки

Столбец	Значение	Комментарии и примеры.
Ячейка	Адреса ячеек с неизвестными
Имя	Имена неизвестных
Результирующее значение	Оптимальные значения неизвестных, полученные в ходе решения задачи.
Целевой коэффициент	Коэффициенты, стоящие при неизвестных в целевой функции.	В данной задаче – % ставки банков.
Допустимое увеличение Допустимое уменьшение	Числа, показывающие, на сколько максимально можно увеличить или уменьшить % ставки банков при сохранении оптимального плана. Целевая функция при этом может измениться.	Проводя анализ данных, можно сделать следующие выводы: Годовой процент 1 банка может колебаться в пределах (8%+ 1Е+30%, 8%-0,5%), 2 банка – (7%+ 1,25%,7%- 1Е+30%), 3 банка – (8%+ 0,5%, 8%- 2,5%), Пример: Предположим, что годовой процент 1 банка увеличился на 1% и составил 8,5%+1%=9,5%. Т.к. для 1 банка увеличение годового процента не ограниченно, то оптимальный план в задаче остался прежним =(11250, 27500,11250), при этом доход D увеличился и составил = 3893,75 руб.

Таблица 7

Раздел Ограничения

Столбец	Примечание	Комментарии и примеры
Ячейка	Адреса ячеек с левыми частями ограничений
Результирующее значение	Значения левых частей ограничений в результате решения задачи
Теневая цена	Теневая цена показывает насколько изменится годовой доход при увеличении правой части ограничения на 1 единицу. + , где - теневая цена.	Пример: Предположим, что правая часть 1-ого ограничения увеличилась на 1, т.е. вкладчик вложил 50001 руб. Тогда годовой доход изменится следующим образом: D= = 3781,25+0,075625= 3893,8279 руб.
Ограничение правая часть	Правые части ограничений
Допустимое увеличение	Число, показывающие, на сколько можно увеличить правые части ограничений сохранении теневой цены. При этом значение целевой функции изменится следующим образом: + , где -величина увеличении ресурса, - теневая цена.	Пример: Если дополнительно вложить еще = 10000 руб., то годовой доход изменится следующим образом: D= = 3781,25+10000*0,075625=4537,5 руб.
Допустимое уменьшение	Число, показывающие, на сколько можно уменьшить правые части ограничений при сохранении теневой цены. При этом значение целевой функции изменится следующим образом: - , где -величина увеличении ресурса, - теневая цена.	Пример: Если уменьшить сумму вклада до 40000руб., = 10000 руб., то годовой доход составит: D= = 3781,25-10000*0,075625=3025 руб.

 

Таблица 8

Тип ресурса	Нормы затрат ресурса на один ковер	Наличие ресурсов (ед.)
Сырье
Рабочее время
Оборудование
Прибыль (руб.)

 

В данном случае, математическая модель аналогична математической модели Задачи 1, но добавляется новое условие xi – целые числа.

Таблица 9

Неизвестные
x1 –количество ковров 1 - ого вида, x2 – –количество ковров 2 - ого вида, x3 –количество ковров 3 - его вида, x4 –количество ковров 4 - ого вида.
Целевая функция	Ограничения
Р=30*x1+25*x2+8*x3+16* x4 (руб.)	3*x1+5*x2+2*x3+4*x4 60, 22*x1+14*x2+18*x3+30*x4 400, 10*x1+14*x2+8*x3+16*x4 120, xi 0, i=1,2,3,4, xi – целые числа.

Данное условие оформляется в окне Поиск решения следующим образом (см. рис. 21):

Рис.21 Добавление ограничения

Примечание: Для задач целочисленной оптимизации не предусмотрено вывода отчета по устойчивости.

 

Транспортная задача

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

Для строительства четырех объектов используется кирпич, изготавливаемый на трех заводах. Ежедневно каждый из заводов может изготавливать 100, 150 и 50 усл. ед. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектов равны 70, 80, 60 и 90 усл. ед. Известны также тарифы перевозок 1 усл. ед. кирпича с каждого из заводов к каждому из строящихся объектов, они заданы матрицей С следующего вида:

. (***)

Составить такой план перевозок кирпича от заводов к стоящимся объектам, при котором общая стоимость перевозок будет минимальной.

 

Представим данные задачи в виде следующей таблицы:

Таблица 10

	Стоимость перевозки 1 усл. ед. кирпича с завода к строящемуся объекту	Возможности заводов
Объекты Заводы
I
II
III
Потребность объектов в кирпиче

В данной задаче потребность всех объектов в кирпиче равна запасам всех заводов (70+80+60+90=100+150+50), т.е. она является закрытой, а следовательно разрешима.

Решение

Элементы модели

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

Цель задачи – минимизировать стоимость перевозок. Т.к. стоимость перевозки 1 усл. ед. от каждого завода к каждому объекту нам известна (см.*) т.о. S будет иметь вид:

S=6*x11+7*x12+3*x13+5*x14+1*x21+2*x22+5*x23+6*x24+

+8*x31+10*x32+20*x33+1*x34 (руб.)

Ограничения

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

 

 

Ограничения «на производство» кирпича:

x11+x12+x13+x14=100, (13)

x21+x22+x23+x24=150, (14)

x31+x32+x33+x34=50, (15)

Ограничения «на потребности» в кирпиче:

x11+x21+x31=70, (16)

x12+x22+x32=80, (17)

x13+x23+x33=60, (18)

x14+x24+x34=90, (19)

xi 0, i=1,2,3,4, (20)

xi – целые числа (21)

Примечание: Ограничения (20) и (21) представляют собой следующие естественные условия: количество перевозимых кирпичей должно быть не отрицательным и целым.

 

Таблица 11

Неизвестные
–количество усл.ед. кирпичей, перевозимых с i – ого завода на j – ый строящийся объект, i =1,2,3, j = 1,2,3,4.
Целевая функция	Ограничения
S=6*x11+7*x12+3*x13+5*x14+ +1*x21+2*x22+5*x23+6*x24+ +8*x31+10*x32+20*x33+1*x34 (руб.)	x11+x12+x13+x14=100, x21+x22+x23+x24=150, x31+x32+x33+x34=50, x11+x21+x31=70, x12+x22+x32=80, x13+x23+x33=60, x14+x24+x34=90 xi 0, i=1,2,3,4, xi – целые числа

Ответ

В результате решения задачи был получен следующий ответ:

x11=0 (с первого завода на первый объект кирпичи не поставляются),

x12=0 (с первого завода на второй объект кирпичи не поставляются),

x13=60 (с первого завода на третий объект необходимо поставить 60 усл ед. кирпичей),

…

X34=50 (с третьего завода на четвертый объект необходимо поставить 50 усл. ед. кирпичей),

.

При этом минимальная стоимость перевозки будет 660 руб., .

Рис. 29 результат решения задачи

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

Изменим условие задачи 4 следующим образом: допустим, что потребность первого завода в кирпиче возросла вдвое и составила 140 ед. кирпича в день. Остальные данные остались неизменными.

Таблица 12

	Стоимость перевозки 1 усл. ед. кирпича с завода к строящемуся объекту	Возможности заводов
Объекты Заводы
I
II
III
Потребность объектов в кирпиче

Данная задаче уже является открытой, т.к. 140+80+60+9>100+150+50, т.е. потребности превышают запасы на 160 ед.

Введем нового поставщика - IV завод с возможностью 160 ед.

Так как груз от фиктивного поставщика к фиктивному потребителю не перевозится, то стоимость перевозок полагается равной нулю.

Таблица 12 примет вид:

Таблица 13

	Стоимость перевозки 1 усл. ед. кирпича с завода к строящемуся объекту	Возможности заводов
Объекты Заводы
I
II
III
IV
Потребность объектов

Данная задача уже является закрытой и решается аналогично задаче

 

Задача о назначениях

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

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

Работники	Работы
	10	12	14
	11	13	14
	10	9	12

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

Решение

Элементы модели

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

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

V будет иметь вид:

V=10*x11+12*x12+14*x13+

+11*x21+13*x22+14*x23+

+10*x31+9*x32+12*x33 ( мин .)

Ограничения

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

 

Каждый рабочий выполняет только одну операцию

x11+x12+x13=1, (22)

x21+x22+x23=1, (23)

x31+x32+x33=1, (24)

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

x11+x21+x31=1, (25)

x12+x22+x32=1, (26)

x13+x23+x33=1, (27)

xi –двоичные (28)

Примечание:

Ограничение 7 представляют собой следующие условие: