Реализация симплекс-метода на компьютере

Пример 4.1 . Фирма выпускает три вида кожаных изделий A, B и C. На изготовление единицы продукции A затрачивается 0, 2 ч работы дубильного участка, 0, 6 ч раскройного участка, 0 ч завершающего участка. На изготовление единицы продукции B – 0, 3; 0, 5 и 0 ч; на изготовление единицы продукции C – 0, 4; 0, 4 и 0, 8 соответственно. Прибыль от единицы продукции вида A составляет 6 ден.ед., вида B – 7 ден.ед., вида C – 10 ден.ед. В течение месяца рабочее время каждого участка ограничено следующим образом:

Дубильного участка – 320 ч; Раскройного участка – 400 ч; Завершающего участка – 160 ч.

Требуется:

1) записать данные задачи в таблицу;

2) составить экономическую модель;

3) Решить задачу с помощью надстройки «Поиск решения»

.

Решение.

1) Составим таблицу.

Ресурсы ( ч )	Потребление ресурсов на единицу продукции	Ограничения на ресурсы ( ч )
А	В	С
Дубильный участок	0, 2	0, 3	0, 4
Раскройный участок	0, 5	0, 5	0, 4
Завершающий участок			0, 8
Прибыль (ден.ед.)

2) Экономическая модель.

 

Пусть выпускается штук изделий вида A, B и C соответственно. Тогда прибыль от продажи всех изделий , и

Ограничения по запасам ресурсов:

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

3) Решение задачи на компьютере с помощью надстройки «Поиск решения». Соответствующая кнопка должна находиться

Установка приложения к ППП Excel пакета «Поиск решения».

Для WINDOWS-3

Открыть файл Excel. В меню «Сервис» выбрать «Надстройки», установить отметку в строке «Поиск решения»

 

Для WINDOWS-7

Откройте файл Excel

Нажмите «Кнопку офис» в левом верхнем углу экрана

 

 

 

Появится вкладка:

Нажать «Параметры Excel»

 

 

Нажать «Надстройки»

Нажать «Перейти»

Поставьте отметку в строке «Поиск решения»

 

 

OK

 

«ДА»

 

После завершения настройки на вкладке «Данные» появляется кнопка «Поиск решения».

 

Создадим экранную форму для решения задачи с помощью надстройки «Поиск решения».

В ячейки B1, C1, D1 запишем обозначения переменных, ячейки B3, C3, D3 служат для машинного подбора их значений, при которых достигается максимум прибыли. Эти ячейки называются изменяемыми.

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

В ячейки B4, C4, D4 запишем коэффициенты целевой функции

а в ячейки B6 – D8 - коэффициенты при соответствующих переменных из системы ограничений:

 

В ячейки G6-G8 внесем запасы ресурсов, а в ячейки F6-F8 – знаки ограничений

В ячейку F3 введём зависимость (формулу ) для целевой функции. Для этого щелкнем курсором на ячейку F3, затем на панели щелкнем кнопку - вставка функции:

на экране появляется диалоговое окно Мастер функций шаг 1 из 2.

В категории на « Математические» выберем функцию СУММПРОИЗВ

ОК

В появившемся окне СУММПРОИЗВ курсором щелкнуть по строке Массив 1 и выделить курсором поле B3-D3 изменяемых переменных.

 

Затем курсором щелкнуть по строке Массив 2 и выделить курсором поле B4 - D4

 

ОК.

 

В ячейке F3 появится 0

 

Введём зависимости для ограничений (левые части неравенств). Для этого

Поставим курсор в ячейку Е6 и снова вызовем вставку функции, а через нее - функцию СУММПРОИЗВ. В строке Массив 1 выделить ячейки B3-D3, нажать на клавиатуре клавишу F4. После чего ячейка F4 будет зафиксирована и не будет «сползать» при протягивании курсора:

 

В строке Массив 2 выделить первую строчку ограничений (ячейки B6-D6)

 

ОК.

После этого в ячейке Е6 появится 0:

 

 

Установите курсор в правый нижний угол ячейки Е6, получите крестик и протяните его вниз по ячейкам Е7 и Е8

 

После этого в ячейках Е7 и Е8 тоже появятся нули:

 

Можно проверить правильность ввода данных в формулах. У нас формулы набраны в ячейке F3 для целевой функции и в ячейках E6- E8 для ограничений. Поставьте курсор, например, на ячейку F3 и дважды щелкните. На экране цветом выделятся введенные ячейки:

 

 

Нажмите «Enter» или просто щелкните любую пустую ячейку.

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

 

Аналогично проверим правильность набора формул в ячейках E7- E8.

Теперь поставьте курсор в ячейку F3 целевой функции и на вкладке Данные выберите Поиск решения.

Появится диалоговое окно:

 

Отметить Максимальному значению

Щелкнуть курсором по полю Изменяемые ячейки и отметить курсором ячейки B3-D3:

Щелкнуть кнопку Добавить и в открывшемся окне Добавление ограничений в разделе Ссылка на ячейку отметить ячейки E7 – E8:

 

 

Поскольку автоматически установленное ограничение < = совпадает с нужным нам, то переходим к разделу Ограничение и в нем отмечаем ячейки G6-G8:

 

 

OK

Теперь нужно задать параметры поиска. Для этого в окне Поиск решения нажать кнопку Параметры.

 

 

Появится окно Параметры поиска решения

 

 

Установить Линейная модель и Неотрицательные значения (оценки линейные, разности прямые, метод поиска Ньютона обычно установлены автоматически )

 

ОК.

В окне Поиск решения нажать кнопку Выполнить

 

Появится окно Результаты поиска решения

 

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

 

 

ОК.

 

Появится таблица с заполненными ячейками B3: D3, Е7: Е9 и максимальным значением целевой функции в ячейке F3

 

a также 3 новых листа: Отчёт по результатам 1, Отчёт по устойчивости 1, Отчет по пределам1.

Итак, максимальная прибыль – 6480 ден.ед. достигается при производстве 640 изделий вида В и 200 изделий вида С. Изделия А выпускать не рекомендуется.

Ресурс дубильного участка используется лишь в количестве 144 часов из 320 часов, т.е. наблюдается простой в работе дубильного участка в размере 320-144=176 часов.

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

 

В отчёте по результатам та же информация, что и в экранной форме:

 

Microsoft Excel 11.0 Отчет по результатам
Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$F$3	Значение ЦФ
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$B$3	Значение x1
	$C$3	Значение x2
	$D$3	Значение x3
Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$E$6	дубильный уч Лев часть		$E$6< =$G$6	не связан.
	$E$7	раскрой Лев часть		$E$7< =$G$7	связанное
	$E$8	заверш. уч. Лев часть		$E$8< =$G$8	связанное

 

 

Рассмотрим отчёт по устойчивости.

 

Microsoft Excel 11.0 Отчет по устойчивости
Изменяемые ячейки
			Результ.	Нормир.	Целевой	Допустимое	Допустимое
	Ячейка	Имя	значение	стоимость	Коэффициент	Увеличение	Уменьшение
	$B$3	Значение x1		-2, 4		2, 4	1E+30
	$C$3	Значение x2				5, 5
	$D$3	Значение x3				1E+30	4, 4
Ограничения
			Результ.	Теневая	Ограничение	Допустимое	Допустимое
	Ячейка	Имя	значение	Цена	Правая часть	Увеличение	Уменьшение
	$E$6	дубильный уч Лев часть				1E+30
	$E$7	раскрой Лев часть
	$E$8	заверш. уч. Лев часть		5, 5

 

Нормированная стоимость изделия – это величина убытков фирмы при принудительном выпуске одного изделия, выпускать которое не рекомендуется. В данном случае при принудительном выпуске одного изделия А убытки составят 2, 4 ден. ед.

Microsoft Excel 11.0 Отчет по устойчивости
Изменяемые ячейки
		Результ.	Нормир.
Ячейка	Имя	значение	стоимость
$B$3	Значение x1		-2, 4
$C$3	Значение x2
$D$3	Значение x3

 

Допустимое увеличение или уменьшение коэффициентов целевой функции.

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

Microsoft Excel 11.0 Отчет по устойчивости
Изменяемые ячейки
			Результ.	Нормир.	Целевой	Допустимое	Допустимое
	Ячейка	Имя	значение	стоимость	Коэффициент	Увеличение	Уменьшение
	$B$3	Значение x1		-2, 4		2, 4	1E+30
	$C$3	Значение x2				5, 5
	$D$3	Значение x3				1E+30	4, 4

 

Итак, выработанный оптимальный план производства не изменится, если прибыль от продажи изделия А будет дальше как угодно уменьшаться или же увеличится не более чем на 2, 4 ден. ед., т.е. до размера 8, 4 ден. ед. Если же прибыль от продажи изделия А увеличится более, чем не 2, 4 ден. ед., т.е. станет больше 8, 4 ден. ед, то производство изделий А станет выгодным, и для определения оптимального плана производства нужно заново решать задачу.

Оптимальный план производства не изменится, если прибыль от продажи изделия В уменьшится не более, чем на 2 ден. ед. или увеличится не более, чем на 5, 5 ден.ед, т.е. будет находиться в пределах [5: 12, 5].

При этом прибыль

будет колебаться от значения

ден.ед,

до значения

ден.ед,

Оптимальный план производства не изменится, если прибыль от продажи изделия С уменьшится не более, чем на 4, 4 ден. ед., увеличение возможно любое.

При этом прибыль будет увеличиваться от значения

ден.ед,

неограниченно.

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

Ограничения
			Результ.	Теневая
	Ячейка	Имя	значение	Цена
	$E$6	дубильный уч Лев часть
	$E$7	раскрой Лев часть
	$E$8	заверш. уч. Лев часть		5, 5

 

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

Ограничения
			Результ.	Теневая	Ограничение	Допустимое	Допустимое
	Ячейка	Имя	значение	Цена	Правая часть	Увеличение	Уменьшение
	$E$6	дубильный уч Лев часть				1E+30
	$E$7	раскрой Лев часть
	$E$8	заверш. уч. Лев часть		5, 5

 

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

мощность дубильного участка будет наращиваться неограниченно, поскольку время его работы и сейчас имеется в избытке, уменьшить время работы дубильного участка можно на 176 часов;

время работы раскройного участка увеличить на 880 часов или сократить на 320 часов;

время работы завершающего участка увеличить на 440 часов или сократить на 160 часов.

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться: