Проверка сбалансированности модели задачи

Модель явля­ется сбалансированной, т.к. суммарный объем производимой продукции в день равен суммарному объему потребности в ней:

235 + 175 + 185 + 175 = 125 + 160 + 60 + 250 + 175.

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

Построение математической модели

Неизвестными в этой задаче являются объемы перевозок. Пусть х_ij - объем перевозок с i -го предприятия в j -й пункт потребления.

Суммарные транспортные расходы - это функционал качества (критерий цели)

F = ,

где c_ij - стоимость перевозки единицы продукции с i-го предприятия в j-й пункт потребления.

Неизвестные в этой задаче должны удовлетворять следующим ограничениям:

ü объемы перевозок не могут быть отрицательными;

ü поскольку модель сбалансирована, то вся продукция долж­на быть вывезена с предприятий, а потребности всех пунк­тов потребления должны быть полностью удовлетворены.

Итак, имеем следующую задачу:

ü найти минимум функционала:

F = min,

ü при ограничениях:

= b_j,, j [ ], = a_i,, i [ ],

x_ij >= 0, i [ ], j [ ],

где а_i - объем производства на i -м предприятии, b_j - спрос в j -м пункте потребления.

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

ü подготовку рабочего листа для задачи необходимо осуществить в соответствии с рисунком 3.1, с приведенными для расчета формулами.

Рисунок 3.1 Исходные данные для решения транспортной задачи

ü ввод данных в окно Поиск решения необходимо произвести в соответ­ствии с рисунком 3.2.

Не следует забывать также об опциях Линейная модель, От­носительная погрешность окна Параметры поиска решения, вызываемого кнопкой в окне Поиск решения (рисунок 3.2).

Рисунок 3.2 Ввод данных в окно Поиск решения для транспортной задачи

ü полученное оптимальное решение представлено на рисунке 3.3.

Рисунок 3.3 Оптимальное решение для транспортной задачи

Вопросы для самоконтроля знаний

4.1 Что такое транспортная задача?

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

4.3 Что такое несбалансированная модель транспортной задачи?

4.4 В какую модель нужно преобразовать транспортную задачу для ее разрешимости?

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

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

Цель работы: Овладеть приемами работы с надстройкой Поиск решения при решении задач по дискретному программированию. Научиться:

ü находить оптимальное решение задачи с помощью надстройки Поиск решения при решении задач по дискретному программированию;

ü создавать отчеты по результатам поиска решения;

ü сохранять параметры модели.

Общие сведения

Дискретное программирование

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

Это, прежде всего, задачи с физической неделимостью многих факторов и объектов расчета.

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

Содержание работы

2.1 Запустить программу MS Excel.

2.2 Создать файл аналогичный примеру 1 (Задача о назначениях).

2.3 Рассмотреть все варианты нахождения оптимального решения в примере 1, установив надстройку Поиск решения.

2.4 Найти оптимальное решение с помощью надстройки Поиск решения) в заданиях для самостоятельного решения из Приложения Г. Вариант задания выбирается по указанию преподавателя.

2.5 Создать один из видов отчетов по результатам поиска решения.

2.6 Ответить на контрольные вопросы.

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

3 Методика выполнения работы. Нахождение оптимального решения задачи с помощью надстройки Поиск решения на примере задачи о назначениях

Работу с надстройкой Поиск решения рассмотрим на примере задачи о начислениях.

Пример. Задача о назначениях

Каждый из преподавателей может провести определенные виды занятий. Почасовая оплата с_ij i -му преподавателю по j -му виду занятий зависит от его квалификации и должности и приведена в таблице 4.1.

 

Таблица 4.1 Стоимости выполнения учебных занятий

Преподаватели	Почасовая оплата занятий, руб
Лекционные	Лабораторные работы	Практические занятия	Прочие виды занятий
Иванов П.С.
Ткаченко В.И.
Власова Н.Н.
Бикбулатов Ф.Р.

 

Необходимо составить план проведения учебных занятий так, чтобы все виды занятий были проведены, каждый преподаватель проводил заня­тия только по одному виду, а суммарная стоимость почасовой оплаты была минимальной.

Решение.