Задача линейного программирования. Симплекс-метод. Применение надстройки «Поиск решения» в MS Excel

Для решения задач линейного программирования симплекс-методом в среде MS Excel заполняются ячейки исходными данными в режиме чисел и формулами математической модели.

MS Excel позволяет получить оптимальное решение без ограничения размерности системы неравенств целевой функции.

Решим задачу о выпускаемых изделиях симплекс-методом применяя надстройку «Поиск решения» в MS Excel.

1. Заполните таблицу Excel в режиме чисел (рис.1)

2. Заполните таблицу Excel в режиме формул (рис.2)

Рис.1 Таблица в режиме чисел

Рис.1 Таблица в режиме формул

Здесь: В9:С9 – результат (оптимальное количество изделий каждого вида);

В6:С6 – коэффициенты целевой функции;

В10 – значение целевой функции;

В3:С5 – коэффициенты ограничений;

D12:D14 – правая часть ограничений;

B12:B14 – вычисляемые (фактические) значения левой части ограничений.

Решим задачу с помощью команды Данные/Поиск решения. На экране появляется диалоговое окно Поиск решения.

В поле Установить целевую функция будет показана ссылка на активную ячейку, т.е. на В10. Причем эта ссылка абсолютная. В секции Равной устанавливаем переключатель Максимальному (минимальному) значению в зависимости от целевой функции. Ограничения устанавливаются с помощью кнопки Добавить, которая вызывает диалоговое окно их ввода Добавление ограничения.

В поле ввода Ссылка на ячейку: указывается адрес ячейки, содержащей формулу левой части ограничения. Затем выбирается из списка знак соотношения. В поле Ограничение указывается адрес ячейки, содержащей правую часть ограничения. Щёлкаем на кнопку Добавить и повторяем до следующего ограничения. После ввода всех ограничений нажимаем ОК.

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

Устанавливаем флажок Сделать переменные без ограничений неотрицательными и выбрать Метод решения Поиск решения линеных задач симплекс-методом. Щёлкаем на кнопке Найти решение.

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

Если вычисления оказались успешными, Excel предъявит следующее окно итогов. Их можно сохранить или отказаться. Кроме того, можно получить один из трёх видов отчётов (Результаты,Устойчивость,Пределы), позволяющие лучше осознать полученные результаты, в том числе, оценить их достоверность.

После найденного решения, в ячейках В9:С9 появится оптимальное количество изделий каждого вида.

При сохранении отчета выберите – Отчет по результатам (рис.3).

Из отчета видно, что ресурс 1 не используется полностью на 150 кг, а ресурс 2 и 3 используется полностью.

В результате получен оптимальный план, при котором изделий 1 вида необходимо выпустить в количестве 58 шт., а изделий 2 вида в количестве 42 шт. При этом прибыль от их реализации максимальная и составляет 4660 тыс.руб.

Рис.3 Отчет по результатам

1. Со станции формирования ежедневно отправляются пассажирские и скорые поезда, составленные из плацкартных, купейных и мягких вагонов. Число мест в плацкартном вагоне – 54, в купейном – 36, в мягком – 18. В таблице указаны состав поезда каждого типа и количество имеющихся в парке вагонов различного типа. Определить число скорых и пассажирских поездов, которые необходимо формировать ежедневно, чтобы число перевозимых пассажиров было максимальным.

1	плац	куп	мягк
скор	2	6	2
пасс	5	3	2
парк	50	60	26

2	плац	куп	мягк
скор	2	6	2
пасс	5	4	2
парк	50	66	26

3	плац	куп	мягк
скор	2	6	2
пасс	5	3	2
парк	55	60	26

4	плац	куп	мягк
скор	2	6	2
пасс	5	4	2
парк	55	66	26

5	плац	куп	мягк
скор	2	7	2
пасс	5	4	2
парк	55	77	28

6	плац	куп	мягк
скор	2	7	2
пасс	5	5	2
парк	55	84	28

7	плац	куп	мягк
скор	4	6	2
пасс	5	3	2
парк	60	60	26

8	плац	куп	мягк
скор	4	6	2
пасс	5	4	2
парк	60	66	26

9	плац	куп	мягк
скор	4	6	2
пасс	5	2	2
парк	60	72	26

10	плац	куп	мягк
скор	2	7	2
пасс	5	6	2
парк	55	91	28

11	плац	куп	мягк
скор	3	7	2
пасс	5	3	2
парк	60	70	28

12	плац	куп	мягк
скор	2	6	2
пасс	5	5	2
парк	50	72	26

13	плац	куп	мягк
скор	3	7	2
пасс	5	4	2
парк	60	70	28

14	плац	куп	мягк
скор	3	7	2
пасс	5	5	2
парк	60	84	28

15	плац	куп	мягк
скор	3	6	2
пасс	5	5	2
парк	55	72	26

16	плац	куп	мягк
скор	3	7	2
пасс	5	6	2
парк	60	91	28

17	плац	куп	мягк
скор	2	8	2
пасс	5	5	2
парк	60	96	30

18	плац	куп	мягк
скор	2	8	2
пасс	5	5	2
парк	60	96	30

19	плац	куп	мягк
скор	2	8	2
пасс	5	6	2
парк	60	104	30

20	плац	куп	мягк
скор	2	8	2
пасс	5	7	2
парк	60	112	30

21	плац	куп	мягк
скор	1	8	2
пасс	5	5	2
парк	55	96	30

22	плац	куп	мягк
скор	1	8	2
пасс	5	6	2
парк	55	104	30

23	плац	куп	мягк
скор	4	7	2
пасс	5	6	2
парк	65	91	28

24	плац	куп	мягк
скор	4	7	2
пасс	5	5	2
парк	65	84	28

25	плац	куп	мягк
скор	4	7	2
пасс	5	3	2
парк	65	70	28

26	плац	куп	мягк
скор	4	7	2
пасс	5	4	2
парк	65	77	28

27	плац	куп	мягк
скор	1	7	2
пасс	5	3	2
парк	50	70	28

28	плац	куп	мягк
скор	1	7	2
пасс	5	4	2
парк	50	77	28

30	плац	куп	мягк
скор	1	7	2
пасс	5	6	2
парк	50	91	28

29	плац	куп	мягк
скор	1	7	2
пасс	5	5	2
парк	50	84	28

Решение транспортных задач

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

	b1	b2	…	bk	…	bg
a1	[c11 x11	[c12 x12	…	[c1k x1k	…	[c1g x1g
a2	[c21 x21	[c22 X22	…	[c2k x2k	…	[c2g x2g
…	…	…	…	…	…	…
ai	[ci2 xi2	[ci2 xi2	…	[cik xik	…	[cig xig
…	…	…	…	…	…	…
ap	[cp2 xp2	[cp2 xp2	…	[cpk xpk	…	[cpg xpg

Если закрытая модель транспортной задачи

Переменные должны удовлетворять условиям

Суммарные затраты на перевозки

Решение такой задачи разбивается на два этапа:

1. Определение опорного (базисного) решения;

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

Для каждого из этих этапов существует несколько методов.

Для построения опорного решения чаще всего используют метод «северо-западного угла» и метод минимальных тарифов.