Моделирование в экономике. Задача линейного программирования

Лабораторная работа №2

Моделирование в экономике. Задача линейного программирования

1.Формулировка задачи. Для изготовления двух видов продукции Р₁ и Р₂ на предприятии используются три вида различного сырья: А₁, А₂, А₃. Запасы сырья каждого вида Аi известны и равны b_i кг, соответственно. Количество единиц сырья Аi, используемое на изготовление единицы продукции вида Р_j , равно а_ij, кг. Величина прибыли, получаемой от реализации единицы продукции Рj, равна с_j ( i =1, 2, 3; j =1, 2). Найти поптимальный лан выпуска продукции, т.е. чтобы при её реализации предприятие получало максимальную прибыль, и определить величину этой максимальной прибыли. При решении задачи учитывать, что переменные удовлетворяют условиям неотрицательности: x₁ ≥ 0; x₂ ≥ 0. Варианты заданий.

№ Варианта	a₁₁	a₂₁	a₃₁	a₁₂	a₂₂	a₃₂	b₁	b₂	b₃	c₁	c₂

Задания к решению задачи.

1) Сформулируйте в словесной форме прямую оптимизационную задачу на максимум получения прибыли для своих данных, заменив названия параметров задачи числами в соответствии с индивидуальным вариантом. Запишите её.

2) Сформулируйте двойственную задачу на минимум стоимости ресурсов в словесной форме для своих данных, заменив названия параметров задачи реальным содержанием. Запишите её.

3) Запишите математические формулировки прямой (1) и двойственной (2) задач:

(1) (2)

4) Замените значения параметров их числовыми значениями в соответствии с вариантом задания (Приведён пример для Варианта №1).

5) Решите обе задачи методом Поиск решения (в EXCEL).

6) Приведите прямую задачу к каноническому виду:

7) Решите прямую задачу (Найдите оптимальный план) Симплекс-методом.

8) Решить двойственную задачу с помощью Теорем двойственности.

9) Убедитесь, что результаты решения Симплекс-методом и методом Поиск решения совпадают.

10) Запишите решения прямой и двойственной задачи в виде:

а) Для прямой задачи:

б)Для двойственной задачи:

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

1.Проверьте соблюдение Теорем двойственности.

Теорема 1: совпадение значений целевой функции для прямой и обратной задач.

Теорема 2:

1)Ресурс i-го вида имеет ненулевую цену (yi), если полностью расходуется в процессе производства (является дефицитным). При этом соответствующее i-му ресурсу выражениев скобках обращается в 0 (3), т.е. соответсвующее ограничение прямой задачи является равенством.

(3)

2)Продукция j-го вида производится (xj> 0), если стоимость затраченных на её производство ресурсов по оптимальным ценам равна прибыли (cj) от её реализации, т.е. соответствующее ограничение двойственной задачи является верным равенством (4):

(4)

2.Проанализируйте использование ресурсов в оптимальном плане и ответьте письменно на следующие вопросы.

- Какие ресурсы используются полностью (дефицитные)?

- Какие ресурсы избыточны?

- Опираться на Таблицу результатов прямой задачи (Поля Cтатус и Разница).

- Чему равна теневая цена избыточных ресурсов (см. Отчёт по устойчивости).

- Сравнить дефицитность ресурсов и приписать им ранг (1 – самый дефицитный, больше всего ограничивает производство).

- Представить данные в виде Таблицы:

Ресурс	Избыточный/дефицитный	Увеличение запаса ресурса выгодно/ нет	Ограничивает производство/не ограничивает производство	Теневая цена	Определить Ранг дефицитности ресурса (1- самый высокий и т.д.)	На сколько руб. изменяется выручка при увеличении запаса ресурса на 1 ед.

3.Определить нижние и верхние границы ресурсов, при которых сохраняется ассортимент выпускаемых продуктов оптимального плана, теневые цены ресурсов, статус ресурсов.

Опираться на Таблицу “Ограничения” Отчёта по устойчивости прямой задачи

Ресурс	Min граница доступного ресурса	Max граница доступного ресурса	Статус ресурсов не меняется при min< =B< =max	Ассортимент товаров не меняется при min< =B< =max	План выпуска товаров меняется при min< =B< =max	Теневая цена ресурса не меняется при min< =B< =max	Теневая цена ресурса меняется при B> max или B< min

4.Найти граничные цены продуктов, в пределах которых оптимальный план не изменяется (Отчёт по устойчивости: Таблица Изменяемые ячейки).

1) Границы цен при сохранении оптимального плана

Про дукт	Min граница цены продукта	Max граница цены продукта	Оптимальный план не меняется при min< =C< =max	Выручка не меняется при min< =C< =max	Существует много планов при C=max или C=min	Оптимальный план Меняется при C> max или C< min

Что происходит со статусом ресурсов при выходе цен продуктов за критические границы? (статус ресурсов может измениться).

5.Определите, как изменится общая стоимость продукции и план ее выпуска при увеличении запасов сырья I и II вида на 2 и 3 единицы соответственно и уменьшении на 3 единицы количества сырья III. Использовать Свойство 2 двойственных оценок и Критические границы ресурсов.

6.Определите целесообразность включения в план изделия " Д" ценой 10 руб/кг, на изготовление 1 кг которого расходуется по 2 кг каждого вида сырья (Использовать Свойство 3 Двойственных оценок)

7. Используя Свойство 4 двойственных оценок, определить взаимозаменяемость 1-го ресурса и остальных с т.зр. сохранения общей прибыли. Привести расчёты.

8. По выполненной Лабораторной работе представить отчет в составе:

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

· Вариант задания.

· Распечатки Листов EXCEL решений прямой задачи, обратной задачи, Отчёта по результатм, Отчёта по устойчивости, Отчёта по пределам

· Выполненные задания по всем пунктам из п.2 “Задания к решению задачи” и п.3 “Анализ решения”.

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

Методические указания.

Пример решения задачи линейного программирования на оптимальное использование ресурсов. Прямая задача.

• Пусть предприятие производит 2 вида продуктов: печенье и бисквиты

• Известен состав печенья и бисквитов

• Известна прибыль от реализации единицы (1 кг) продукции

• Известны запасы всех ресурсов

• Известно, сколько каждого ресурса требуется на производство единицы (1 кг) каждого продукта

• Составление модели начинается с введения переменных.

- x1 - объем производства Печенья

- x2 - объем производства Бисквитов.

• Найти наилучший (оптимальный) производственный план – получить максимальную прибыль от реализации печенья и бисквитов.

……….

Все исходные данные представим в виде Таблицы:

Затраты ресурса на 1 кг продукта

Печенье Бисквиты Доступный фонд ресурса

X₁ X₂ B_j

Выручка от 1 кг продукта ( C_i ) (руб.) – в строке

Вид ресурса ( a_ij):

Мука 0, 5 0, 3

масло 0, 3 0, 06

Яйца 0, 18 0, 6

Сахар 0, 2 0, 3

Труд 0, 07 0, 09

оборуд по тесту 0, 015 0, 006

оборуд.по выпечке- 0, 0075 0, 015

спрос/ печенье

Спрос/бисквиты

Дать математическую формулировку задачи:

- Граничные условия представить в виде неравенств

- Записать выражение для целевой функции

Граничные условия: Целевая функция:

Двойственная задача.

Смысл двойственной задачи.

Предприятие 1 (П1), производящее продукцию, продаёт ресурсы Предприятию 2 (П2).

Цель П1:

- Отражена в ограничениях двойственной задачи

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

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

- кол. 1-го ресурса на единицу продукции *Цена 1-го ресурса + кол. 2-го ресурса единицу продукции * Цена 2-го ресурса +…> = прибыль от реализацииединицы i-го продукта (руб/кг продукта)

Цель П2:

- Минимизировать суммарную стоимость ресурсов;

- Определяется целевой функцией:

запасы 1-го ресурса*Цена 1-го ресурса + запасы 2-го ресурса * Цена 2-го ресурса +… => min

2) Правила получения двойственной задачи из задачи исходной.

- Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.

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

- В исходной ЗЛП все функциональные ограничения - неравенства вида “≤ ”, а в задаче, двойственной ей, - неравенства вида “≥ ”.

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

- Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.

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

3) Словесная формулировки двойственной задачи.

Найти такие цены ресурсов (yi), чтобы суммарная стоимость ресурсов была минимальна (целевая задача), а cтоимость ресурсов, затрачиваемых на производство единицы (например, 1 кг) продукции каждого вида, была не меньшеприбыли от реализации единицы продукции этого вида (граничные условия).

4)Математическая формулировки двойственной задачи.

Целевая функция (Ищем минимальную стоимость ресурсов):

Граничные условия:

Анализ результатов.

Отчёт по результатам

Включает 3 Таблицы:

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

- исходное - до начала вычислений (в поле Исходное значение);

- итоговое – после оптимизационных вычислений (в поле Результаты).

2 Таблица Изменяемые ячейки:

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

3 Таблица Ограничения:

- Поле Значения – количество используемого ресурса для реализации плана (кг);

- Поле Статус – статус ограничений (связанное – при полном использовании ресурса; несвязанное – при избытке ресурса);

- Поле Разница - разность между доступным количеством ресурса и использованным для выполнения плана.

Отчёт по Устойчивости.

Содержит информацию, позволяющую провести постоптимизационный анализ решения задачи.

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

Содержит 2 Таблицы:

1-я Таблица Изменяемые ячейки:

- Поле Результ. Значение – содержит кол-ва выпуска продуктов (x₁ и x₂) для Оптимального плана ( кг );

- Поле Целевой коэф-т: в нашем случае – это выручка за реализацию единицы продукта ( руб./кг );

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

27-7.8≤ с ≤ 27+21, т.е. при 19.2≤ с ≤ 48

- Поле Нормир.стоимость – потери целевой функции (руб.) от выпуска единицы ( 1 кг ) невыгодного товара, т.е. который отсутствует в оптимальном плане. В нашем примере в оптимальном плане производятся оба вида продукции. Поэтому нормированная стоимость равна 0;

- Для невыпускаемой продукции нормированная стоимость показывает, насколько изменится целевая функция при принудительном включении единицы этой продукции в оптимальное решение;

2-я Таблица Ограничения.

Содержит:

- Поле Результ. Значение – величины использованных ресурсов (левые части ограничений, кг ) при оптимальном плане выпуска продукции;

- Поле Теневая цена - оптимальные значения двойственных переменных, которые показывают, как изменится целевая функция (в руб. ) при изменении соответствующего запаса ресурса на единицу (например, на 1 кг ); Имеет размерность руб./кг ресурса; Например, при увеличении муки на 2 кг и масла на 3 кг доход изменится на:

46.7 руб/кг * 2кг+0руб/кг*3 кг=93.4 руб.

- Поле Ограничение Правая часть · исходные запасы ресурсов (правые части ограничений, кг );

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

- То есть при увеличении запасов муки на 10 кг её теневая цена останется прежней, поэтому доход увеличится на 10кг*46.7 руб/кг=467 руб. А при увеличении муки на 76 кг её теневая цена изменится, поэтому ничего про дополнительный доход без дополнительного исследования сказать нельзя, так как мы вышли за допустимые пределы изменения муки (увеличение на 75 кг).

3)Отчёт по Пределам.

Состоит из 2-х таблиц.

· Целевое

· Изменяемое

1-я Таблица Целевое:

- Поле Значение – значение целевой функции (в нашем примере - выручка) в оптимальном решении ( руб.).

2-я таблица Изменяемое:

- Поле Значение – значение выпуска продукции в оптимальном решении ( кг ).

- Поле Целевой результат – чему равна выручка ( кг ) от выпуска продукции, если:

ü Данный продукт выпускается на нижнем (или верхнем пределе):

ü Остальные продукты выпускаются по оптимальному плану.

- Поля Верхний предел и Нижний предел - приводятся нижние и верхние пределы выпуска указанного продукта ( кг ).

Целевой результат для нижнего предела Печенья:

32*0+27*667=18000 (руб.)

Целевой результат для нижнего предела Бисквитов:

32*1250+27*0=40000 (руб.)

Целевой результат для верхнего предела любого продукта: 32*1250+27*667=58000 (руб.)

Примечание: Аналогично решается двойственная задача с помощью механизма “Поиск решения”.

На рисунке приведён лист EXCEL с данными для двойственной задачи и результатом её решения.

Теоремы двойственности.

Теоремы двойственности устанавливают связь между оптимальными планами взаимно двойственных задач.

Теорема 1.

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

Т.е.: прибыль предприятия П1 от реализации продукции при оптимальном плане равна оптимальным затратам на приобретение ресурсов предприятием П2.

Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы.

Теорема 2 (о дополняющей нежесткости).

Для того чтобы план и план являлись оптимальными решениями, соответственно, задач (1) и (2), необходимо и достаточно, чтобы выполнялись следующие соотношения:

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