Решение задач линейного программирования (графический метод, симплекс-метод, двойственная задача, транспортная задача, задача о назначениях)

Полное описание заданий с исходными данными представлено в Демо-файле "Описание работы".

Если вам нужна работа с другими исходными данными (другой вариант), то напишите мне в личку Marka37 (https://studwork.ru/mail/36969) и обсудим подробности.

Работа выполнена в 2020 году. Объем работы – 33 стр. Оформление в Word. Шрифт – 14, интервал – 1,5. К архиву также прикреплен файл Excel с решенными задачи №3.

Работа сделана с подробными пояснениями к решению.

Задание 1

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

a. Записать эту задачу в матричной форме.

b. Записать каноническую задачу, соответствующую данной.

c. Решить первоначальную задачу геометрически.

d. Найти начальный базисный план канонической задачи с помощью искусственных переменных.

e. Решить каноническую задачу симплекс-методом.

f. Написать двойственную задачу к данной задаче в матричной и развернутой формах.

g. Найти решение двойственной задачи и доказать его оптимальность с помощью теоремы двойственности.

max(2x1+x2),

4x1+3x2 >= 12,

x1+2x2 <= 8,

2x1+x2 <= 10,

x1, x2 >= 0.

Задание 2

Однородный груз сосредоточен в m пунктах отправления (на m складах) A1, A2,...Am и должен быть распределен между n получателей B1, B2,...Bn. Пусть - ai объем запаса груза в пункте Ai, bj - объем заявки в пункта Bj, cij - стоимость перевозки единицы груза из пункта Ai в пункт Bj.

a. Составить математическую модель с учетом данных задания и определить возможность удовлетворения всех заявок имеющимися запасами.

b. Определить начальный базисный план транспортной задачи методом северо-западного угла и указать стоимость перевозки груза по этому плану.

с. Определить начальный базисный план транспортной задачи методом наименьшей стоимости и указать стоимость перевозки груза по этому плану.

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

Исходные данные:

4 5 6 7 7 100

5 4 4 4 8 120

4 6 5 7 6 80

3 3 5 5 11 100

100 80 120 130 110

Задание 3

Составить математическую модель и найти оптимальное решение, используя процедуру «поиск решения» («solver») MS Excel. Ответ записать в развернутой форме.

Распределить станки четырех типов по пяти видам работ. В наличии имеется 25, 30, 20, 30 станков каждого типа соответственно. Каждый вид работ заключается в выполнении 20, 20, 30, 10 и 25 операций соответственно. На станке типа 4 не может выполняться работа типа 4. Стоимость одной операции, осуществляемой на станках разный типов для разных работ приведена в табл. Определить оптимальное распределение станков по работам.

Таблица

Тип станков Тип работ

1 2 3 4 5

1 10 2 3 15 9

2 5 10 15 2 4

3 15 5 14 7 15

4 20 15 13 - 8

Задание 1………… 3

Задание 2………… 16

Задание 3………… 27

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

1. Александрова И.А., Гончаренко В.М. Методы оптимальных решений. Руководство к решению задач. М.: Финуниверситет, 2012. - 114 с.

2. Казанская О.В., Юн С.Г., Альсова О.К. Модели и методы оптимизации. Практикум: уч. пособие - Новосибирск: Изд-во НГТУ, 2012. - 204 с.

............

............