Решение задач линейного программирования

Размещено на http://www.Allbest.ru/

Задача 1

Графический метод решения задач линейного программирования

Решить графически ЗЛП:

Решение

Первое ограничение . Решением этого неравенства является полуплоскость, лежащая ниже прямой (I), проходящей через точки (0;20) и (4;0). Второе ограничение . Решением этого неравенства является полуплоскость, лежащая выше прямой (II), проходящей через точки (0;1) и (3/2;0). Третье ограничение . Решением этого неравенства является полуплоскость, лежащая ниже прямой (III), проходящей через точки (0;-4) и (2;0). Ограничения задают первую полуплоскость.

Получили общую область допустимых решений для всех неравенств ABCDЕ (Рис. 1).

Построим линию уровня, для чего приравняем целевую функцию к нулю: . Линия уровня изображена на рис. 1. пунктирной прямой. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е. (1;5). Чтобы построить такой вектор, соединяем эту точку с началом координат.



Рис. 1

При определении максимума целевой функции движение линии уровня будем осуществлять до её пересечения с точкой А с координатами (0; 20) - в направлении вектора градиента; далее она выходит из области допустимых решений. В этой точке достигается максимум целевой функции. max f(X) = 0•1 +20•5 = 100 и достигается при х ₁ = 0 и х₂ = 20.

При определении минимума целевой функции движение линии уровня будем осуществлять до её пересечения с точкой С с координатами (1,5; 0) - в направлении, противоположном вектору градиенту; далее она выходит из области допустимых решений. В этой точке достигается минимум целевой функции. min f( X ) = 1•1,5+5•0 = 1,5 и достигается при х ₁ = 1,5 и х₂ = 0.

Задача 2

Симплекс-метод решения задачи линейного программирования

Найти максимум целевой функции

Решение

Шаг 1. Приведем задачу к канонической форме, т.е. добавим в ограничения новые неотрицательные переменные с коэффициентами +1 или -1 так, чтобы неравенства превратились в равенства:

В целевую функцию эти переменные включим с коэффициентом 0:

Шаг 2. Выбор начального базиса и заполнение начальной симплекс- таблицы. В качестве начального базиса выберем линейно независимые векторы матрицы коэффициентов ограничений, включающие в себя новые независимые переменные. Тогда начальное базисное решение будет иметь вид: X = (0, 0, 20, 12)^Т

Заполним начальную таблицу:

Базис	Переменные задачи	bi
	x1	x2	x3	x4
X3	1	4	1	0	20
X4	2	1	0	1	12
?	-4	-1	0	0

Первый столбец (кроме последней строки) содержит наименования базисных переменных. Следующие 4 столбца - коэффициенты a_ij при переменных в ограничениях. Последний столбец содержит коэффициенты правой части ограничений b_i . Последняя строка (?) содержит симплекс-разности, которые на первом шаге равны коэффициентам целевой функции, взятым с обратным знаком.

Шаг 3. Проверка текущего решения на оптимальность. Критерием оптимальности является выполнение условия неотрицательности всех симплекс-разностей ?. Если это условие выполнено, то текущее решение оптимально.

В нашем случае имеются две отрицательные разности: в столбцах x₁ и х₂. Решение неоптимально.

Шаг 4. Выбор направления улучшения решения и определение параметра

В нашем случае два отрицательных значения ? дают два возможных направления улучшения. Выберем столбец с минимальным значением отрицательной разности - столбец 1. Тем самым мы вводим в базис новый элемент x₁. После выбора направления

необходимо проверить, чтобы среди элементов вектора A₁ был хотя бы один положительный элемент. В противном случае целевая функция неограничена на множестве решений и ЗЛП неразрешима.

Вычисляем параметр

Во втором столбце среди коэффициентов при x₂ оба положительных, то получим

Итак, элемент x₁ заменяет элемент x₄ в базисе. Поделим на 2 всю вторую строку.

Операциями над строками в целом необходимо добиться, чтобы в столбце x₂ выше и ниже строки x₃ остались одни нули:

из строки x₄ вычтем строку x₃

к строке ? прибавим 4 строки x₃

Базис	Переменные задачи	bi
	x1	x2	x3	x4
X3	0	-7/2	-1	1/2	-14
X1	1	1/2	0	1/2	6
?	0	1	0	2

В соответствии с шагом 3 видим, что полученное решение оптимально.

Все разности в строке ? неотрицательны, следовательно, мы получили оптимальное решение: x₁ = 6 x₂ = 0 x₃ = -14, x₄ = 0.

Значение целевой функции равно 24.

Задача 3

Сформулировать и решить двойственную задачу для задачи №1.

Решение

Исходная задача содержит три ограничения. Следовательно, в двойственной задаче 3 неизвестных: у₁ - двойственная оценка первого ограничения у₂ - двойственная оценка второго ограничения; у₃ - двойственная оценка третьего ограничения

Рассмотрим прямую задачу на максимум.

,

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

Число ограничений в системе двойственной задачи равно числу переменных в исходной задаче. В правых частях ограничений двойственной задачи стоят коэффициенты при неизвестных в целевой функции исходной задачи. Левая часть ограничений определяет стоимость ресурсов, необходимых для получения единицы смеси:

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

Тогда

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

если х _j > 0, то

В нашей задаче

х₁ = 0 и х₂ = 20> 0, поэтому второе ограничение двойственной задачи обращается в равенства:

Проверим выполнение первой теоремы двойственности:

Это означает, что оптимальный план двойственной задачи (5;0;0) определён верно.

Задача 4

Решить задачу №2 на компьютере с помощью мастера поиска решений

Решение

Для решения используем электронные таблицы MS Excel.

На рис. 2 представлена исходная информация, необходимая для решения задачи. В ячейках А3 и В3 установлены нули как начальное приближение. В ячейках А7 и А8 помещены коэффициенты целевой функции. В ячейках А11:В12 помещены коэффициенты всех трех ограничений. В ячейках Е11:Е12 помещены знаки ограничений. Это справочные элементы и нужны только нам. Для программы решения задач линейного программирования они не требуются. В ячейках F11:F12 помещены правые части ограничений. Теперь, необходимо задать формулы расчета целевой функции и левых частей ограничений. Если посмотреть на нашу таблицу и формулу целевой функции, то можно записать:

Ц = А7*А3+В7*В3

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

Рис. 1. Исходная информация для решения задачи линейного программирования

Поместим формулу вычисления целевой функции в ячейку D7. Устанавливаем курсор в эту ячейку, нажимаем в строке ввода функции "fx" и выбираем из списка функцию «СУММПРОИЗВ» (рис. 2).

Рис. 2. Выбор функции СУММПРОИЗВ

Далее появляется окно ввода аргументов функции. После нажатия правой кнопки в окне ввода «Массив 1» на рабочем листе активизируется окно ввода первого набора. Мышкой выбирается прямоугольная область, содержащая элементы первого массива. Это - значения переменных, т.е. ячейки А3:В3. То же выполняем и для второго массива. Это - коэффициенты целевой функции, т.е. ячейки А7:В7. Завершается операция нажатием кнопки «ОК»

Рис. 3. Окно ввода аргументов

Точно также в ячейки D11:D13 вводятся формулы для вычисления левых частей неравенств. Введенные формулы показаны на рис. 4.

Рис. 4. Отображение введенных формул

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

Для решения задачи необходимо вызвать соответствующий мастер «Поиск решения».последовательностью выбора команд меню: «Сервис» Появляется соответствующая панель (рис. 5).

В окне «Целевая ячейка» указываем ее адрес: D7. В пункте «Оптимизация результата» помечаем окошко «Максимум». В окне «Путем изменения ячеек» указываем адреса наших переменных А3:В3.

В окнах ввода ограничений под общим именем «Ограничительные условия» указываем: в окнах «Ссылка на ячейку» вводим адреса ячеек, в которых содержатся формулы вычисления левых частей неравенств (D11:D12); в окнах «Операция» выбираем либо знаки неравенств, либо типы переменных; в окнах «Значение» указываем адреса ячеек, в которых находятся числовые ограничения неравенств (F11:F12)

Рис. 5 Ввод целевой функции и ограничений в мастер поиска решений

После нажатия кнопки «Решить» появляется сообщение о результате работы программы

Рис. 6. Информационное сообщение о выполнении программы

После нажатия кнопки «Сохранить результат» происходит возврат в рабочий лист, на котором сохранены результаты расчета (рис. 7).

Рис. 7. Результаты расчета

Итак, было получено решение

x₁ = 6; x₂ = 0. Значение целевой функции равно 24

Все ограничения выполнены, причем второе ограничение дало равенство, а первое строгое неравенство.

Задача 5

графический симплекс еxсel линейный программирование

Транспортная задача. Решить транспортную задачу средствами MS Exсel (найти минимальную стоимость перевозок. В таблице указаны стоимости перевозок (матрица цен)

	Потребители
Поставщики	А1	А2	А3	А4	А5	Наличие
В1	223	180	274	122	264	1063
В2	212	278	331	125	246	1192
В3	240	183	352	132	272	1179
В4	247	110	278	101	207	943
Потребности	922	751	1235	480	989

Решение

Сначала сформулируем экономико-математическую модель задачи.

1. Потребности потребителей равны мощностям поставщиков:

(922+751+1235+480+989) = (1063+1192+1179+943) = 4377

Задача относится к задачам закрытого типа

2. Обозначим x_ij - количество товара, поставляемого от поставщика № i к потребителю № j.

3. Обозначим a_ij - стоимость перевозки одной единицы товара, при поставках от поставщика №i к потребителю №j.

4. Составим целевую функцию:

Составим ограничения:

а) каждому потребителю нужно поставить столько, сколько требуется;

б) - каждый поставщик поставил то, что могла.

в) - объемы поставок не могут быть отрицательными.

На рис. 8 представлена подготовительная часть работы. Целевая функция находится как сумма произведений объемов поставок на их стоимость или СУММПРОИЗВ(B5:F8;B14:F17). Эта формула помещена в ячейку D19 (рис. 8). Аналогично вводятся формулы для расчета левых частей ограничений. Например, в ячейке В10 находится сумма ячеек В5:В8 (это сумма поставок в первый город от каждой станции). Аналогичные суммы находятся в ячейках C10:F10. В ячейке H5 находится сумма ячеек B5:F5 (количество отгруженного от поставщика №1). В ячейках H6:H8 находятся объемы поставок от поставщиков 2, 3, 4 соответственно.

Рис. 8. Подготовка таблицы транспортной задачи

После ввода рабочих формул вызываем мастер поиска решений «Поиск решения» через пункты меню «Сервис»

На панели «Поиск решения» (рис. 9) вводим адрес целевой функции (D19), указываем, что необходимо найти минимум, отмечаем адреса переменных (B5:F8) и вводим ограничения.

Рис. 9. Ввод параметров и ограничений

После нажатия кнопки «Выполнить» появится информационное сообщение о найденном решении (рис. 10).



Рис. 10. Информационное сообщение

Результаты расчетов появятся после нажатия кнопки «Сохранить результат» (рис. 11).

Рис. 11. Результаты расчетов

Как видно из рис. 11, все ограничения выполнены, минимальные затраты составляют 941200 единиц.

Задача 6

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

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

	Сотрудник
Рабочее место	А1	А2	А3	А4	А5
В1	-	56	77	20	83
В2	80	95	87	76	59
В3	77	91	29	83	69
В4	55	34	58	45	21
В5	90	45	-	33	89

Решение

В цехе некоторого завода стоит пять станков, количество рабочих в цехе равно пяти. Рабочий 1 не может работать на станке 1, а рабочий 3 - на станке 5. В соответствии с квалификацией рабочих начальник цеха в баллах оценил эффективность работы каждого из рабочих на каждом из станков (в 100-бальной шкале). Решим эту задачу в табличном процессоре MS Excel

Первый шаг: подготовка исходных данных и ввод функций (рис. 12). Сначала оформим две таблицы. «Таблица эффективности» (ячейки A1:F8) содержит исходную табл. Отличие - прочерки были заменены нулями (ячейки В4, F8). «Таблица назначений» (ячейки A10:F17) в ячейках В13:F17 содержит переменные назначения. Числа в этих ячейках могут принимать только два значения: 1 - если рабочий распределен на работу с данным станком; 0 - если не распределен. Изначально везде ставим нули.

Рис. 12. Подготовка исходных данных

«Целевая функция» в ячейке В20 содержит значение эффективности назначений, численно равное произведению переменных назначений на эффективность соответствующего назначения. Эта величина задается функцией «Сумма произведений»: = СУММПРОИЗВ(B4:F8;B13:F17)

В строке «Сумма» в ячейках B18:F18 содержатся суммы переменных назначения по столбцам. Так, в ячейке В18 содержится сумма ячеек В13:В17 (количество назначений на первое рабочее место). Эта величина вычисляется при помощи функции SUM: = sum(B13:B17). В столбце «Сумма» в ячейках G13:G17 содержатся суммы горизонтальных ячеек (общее количество назначений для каждого рабочего). Это задается той же функцией.

Строка и столбец «Границы» указывают граничные значения для количества назначений: в строке - количество людей на одно рабочее место; в столбце - количество рабочих мест на одного человека.

Второй шаг: решение оптимизационной задачи. Для решения оптимизационных задач вызывается через пункты меню «Сервис» инструмент - Поиск решений. Аналогично предыдущим задачам устанавливаем целевую функцию - максимум, ячейки изменяемые и ограничения по задаче (рис. 13)

Рис. 13. Установка параметров модели

1-е ограничение: все значения целые

2-е ограничение: оно является множественным, сравнение проводится по пяти парам (каждая нижняя ячейка равна соответствующей верхней). Смысл: каждый рабочий назначается на одно рабочее место

3-ограничение: переменная назначения В13 (назначение первого рабочего на первое рабочее место) равна нулю.

4-е ограничение: переменная назначения D17 (назначение третьего рабочего на пятое рабочее место) равна нулю.

5-е ограничение: множественное, сравнение проводится сразу по пяти парам ячеек (каждая левая ячейка не больше соответствующей правой). Смысл: каждому рабочему месту назначается не более одного рабочего.

Затем переходим на вкладку «параметры» (рис. 14). Выбираем пункты: «Линейная модель», «Неотрицательные значения»

Рис. 14. Установка параметров поиска решений

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

Рис. 15. Информационное сообщение

После нажатия кнопки «ОК» решение будет выведено на рабочий лист (рис. 16).

Рис. 16. Решение задачи

Т.е. в данных условиях при данных ограничениях решение задачи невозможно.

Задача 7

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

В таблице даны доходности акций (в %), их риски (средние квадратические отклонения доходности ), таблица коэффициентов парной корреляции R. Найти распределение капитала по акциям, если минимальная доходность равна K (%), при минимальном риске .

Акция	Доходность	Риск
А1	12	4
А2	9	2
А3	9	2
А4	10	2
К = 11



Решение

Целевая функция имеет вид:

Ограничения:

Решение будем искать в табличном процессоре Excel при помощи мастера поиска решений. Шаги решения следующие.

1) Формируем таблицы 1 и 2.

2) Резервируем место для изменяемых переменных x1, x2, x3.

3) Транспонируем строку изменяемых переменных.

4) Рассчитываем матрицу ковариаций по формуле

5) Вычисляем дисперсию портфеля как функцию трех переменных (x1, x2, x3):

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

На рис. 17 представлен общий вид рабочего листа.

Рис. 17. Подготовка исходных данных и формул

На рис. 18 представлены все введенные формулы

Рис. 18. Расчетные формулы

После подготовки данных вызываем мастер поиска решения через пункты меню «Данные» ==> «Поиск решения». Появляется панель «Поиск решения» (рис. 19). В строке «Установить целевую ячейку» указываем адрес В28 - в ней находится формула расчета дисперсии портфеля. Помечаем «Равной минимальному значению». В окне «Изменяя ячейки» указываем адреса переменных (B14:F14). Далее, каждый раз нажимая кнопку «Добавить», вводим ограничения.

Рис. 19. Установка параметров мастера поиска решения

После ввода последнего ограничения нажимаем кнопку «Выполнить». Появляется информационное окно о нахождении решения (рис. 20).

Рис. 20. Информационное сообщение

После нажатия кнопки «ОК» на рабочем листе появляются числовые данные решения (рис. 21)

Рис. 21. Результаты решения

Итак, на акции A1 следует потратить 50,00% капитала, на акции А2 - 0%, на акции А3 - 0%, на акции А4 - 50,00%. Доходность составит 11%, а минимальная дисперсия - 5,96.

Задача 9

Модель Леонтьева

Предприятие состоит из двух основных цехов и одного вспомогательного, каждый из которых выпускает один вид продукции. Известны расходные коэффициенты x_ij (прямые затраты) единиц продукции i -го цеха, используемые как промежуточный продукт для выпуска единицы продукции j -го цеха, а также количество единиц i y продукции i -го цеха, предназначенных для реализации (конечный продукт).

Определить:

1. коэффициенты полных затрат;

2. валовой выпуск (план) для каждого цеха;

3. производственную программу цехов;

4. объем валового выпуска, если конечное потребление продукции каждого цеха увеличится на 50, 25, 40 единиц соответственно.

Матрица коэффициентов прямых затрат (А)	Конечный продукт

Решение

Составим необходимые исходные таблицы (рис. 22).

Рис. 22. Таблица исходных данных

1) Определим коэффициенты полных затрат как элементы матрицы (E - A)^-1: используя функцию МОБР для нахождения обратной матрицы в Excel (рис.23-24)

2) валовой выпуск для каждого цеха определим из равенства:

X = (E - A)^-1Y

Используем функцию МУМНОЖ (рис. 23-24)

Следовательно, валовой выпуск для каждого цеха равен х₁ = 240, х₂ = 339 и х₃ = 236.

3) производственную программу цехов определим из соотношения:

x_ij = a_ijx_j (j = 1, 2, 3; i = 1, 2, 3) с помощью функции МУМНОЖ

Рис. 23. Формулы для расчета коэффициентов полных затрат и валового выпуска для каждого цеха

Рис. 24. Расчет коэффициентов полных затрат и валового выпуска для каждого цеха

Рис. 25. Расчет производственной программы цехов

В результате получим следующую балансовую таблицу (с округлением):

Цеха	Внутрипроизводственное потребление xij	Итого xij	Конечный продукт yi	Валовой выпуск xi
	I	II	III
I	46	64	0	110	130	240
II	10	68	61	139	200	339
III	0	98	38	136	100	236

4) объем валового выпуска, если конечное потребление продукции каждого цеха увеличится на 50, 25, 40 единиц соответственно

Вектор

Аналогично п.2. вычисляем валовой выпуск. Результат расчетов представлен на рис. 25

Рис. 25. Решение задачи

Новый валовой выпуск составил:

Вектор

Размещено на Allbest.ru

...