Организация решения задач исследования операций в MATHCAD

Имомов, А. И. Организация решения задач исследования операций в MATHCAD / А. И. Имомов, Б. С. Эргашев. — Текст : непосредственный // Молодой ученый. — 2015. — № 8 (88). — С. 5-10. — URL: https://moluch.ru/archive/88/17276/ (дата обращения: 26.06.2022).

Основная цель работы — показать, как решаются основные задачи исследования операций, такие как задача линейного программирования, транспортная задача, задача о назначении, задача о коммивояжере, матричная игра в MathCAD.

Ключевые слова: исследование операций, задача линейного программирования, транспортная задача, задача о назначении, задача о коммивояжере, матричная игра, решения задач в MathCAD.

1. Управление и планирование являются наиболее сложными функциями в работе предприятий, фирм, служб администраций всех уровней. Долгое время они являлись монополией человека с соответствующей подготовкой и опытом работы [1–3].

Создание компьютеров и программных средств создало огромные возможности для развития науки, совершенствования методов планирования и управления производством. Однако без строгих формулировок задач, без математического описания процессов современный уровень управления и планирования не может быть достигнут. В последнее время появились математические системы- математические программы, позволяющие решить многие задачи без составления компьютерных программ, такие как MathCAD, Maple, Mathematica и т. д. [3–5].

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

Требуется найти максимум или минимум функции

где , — функции, — параметры управления [1–3].

Выражение (1) называется функцией цели. Условия (2),(3) представляют собой ограничения поставленной задачи. Условия (3) справедливы для многих задач, особенно экономических, когда параметры управления по своему физическому смыслу не могут быть отрицательными. Среди условий задачи могут быть равенства.

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

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

В задаче линейного программирования целевая функция и ограничения линейны:

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

Каноническая задача линейного программирования решается с помощью хорошо известного симплекс метода [1–3]. Здесь мы покажем, как можно решить задачу линейного программирования с помощью математической системы MathCAD.

Решим задачу ([1],21.1). После знака // записываем замечание-смысл команд MathCAD.

ORIGIN: =1 m: =2 n: =4 i: =1..m j: =1..n // ввод конечных значений индексов

// матрица и вектор ограничений

Given // обращение к внутренней функции

Переменная введена для экономии места. Здесь и дальше в блоке Given …Minimize знаки равенств и неравенств жирные. Они набираются в панели MathCAD булево.

3. Решение транспортной задачи в MathCAD. Задачи о назначении и коммивояжере.

В организации перевозок некоторого продукта (груза) между пунктами его производства , , и пунктами потребления , , возникает транспортная задача. Каждый пункт производства характеризуется запасом продукта . Каждый пункт потребления характеризуется потребностью в продукте , . Сеть дорог, соединяющая систему рассматриваемых пунктов, моделируется с помощью матрицы . Элемент представляет собой нормы затрат на перевозку единицы груза из пункта производства в пункт потребления . Через обозначим количество продукта, перевозимого из пункта в пункт . Тогда план перевозок груза представляется в виде матрицы:

Транспортная задача ставиться так:

Для решения закрытой транспортной задачи, т. е. для случая , хорошо известным методом является метод потенциалов [1–3].

С транспортной задачей связаны задачи о назначении и о коммивояжере.

Задача о назначении формулируется таким образом: для реализации производственного процесса необходимо выполнить операций. Имеется рабочих, которые способны осуществить их, и время (затраты) выполнения каждым рабочим любой из операций. Требуется определить: кто и какую операцию должен выполнить, чтобы суммарное время (затраты) выполнения всего производственного процесса было минимально. Возможны и другие постановки.

Формализация задачи. Введём матрицу, , где при и при . Тогда каждый рабочий может выполнить лишь одну операцию и справедливо ограничение:

Каждая операция может выполняться лишь одним рабочим и справедливо ограничение:

Матрица системы (10,11) имеет ранг , т. е. из неизвестных являются свободными.

Если обозначить себестоимость выполнения операции рабочим через , то суммарная себестоимость выполнения всех работ будет:

Задача о назначении заключается в минимизации сумму (12) при выполнении ограничений (10), (11) и . Для решения задачи о назначении разработан венгерский метод [1–3]. В решении задачи в матрице , в главной диагонали могут стоять либо 1 либо 0, но в каждой строке и столбце могуть стоять только по одной 1. Матрица С есть матрица себестоимости выполнения соответствующих операций.

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

Задача о коммивояжере формализуется как задача о назначении, но только в матрице решений , в главной диагонали всегда должна стоять 0. Кроме того, в матрице С в главной диогонали должны стоять большие числа.

Здесь мы покажем, как можно решить транспортную задачу, задачи о назначении и о коммивояжере с помощью математической системы MathCAD. Ясно, что задачи о назначении и о коммивояжере являются частными случаями транспортной задачи.

Решим сначала транспортную задачу ([1],23.1).

ORIGIN: =1 m:=3 n: =4 i: =1..m j: =1..n // ввод конечных значений индексов